（2）模拟退火(SA, Simulated Annealing)思想 爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以前图为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。
（3）关于爬山算法与模拟退火，有一个有趣的比喻
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值；
模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
21、 LAR路由协议中的期望域和寻找域
·期望域（Expected Zone）：可能出现的区域 ·寻找域（Request Zone）：限定一个路由请求区域，只有在寻找域中的节点才转发RREQ（广播路由请求分组）。为了增加到达目的节点的成功率，寻找域应该包括期望域以及期望域以外的其他区域。
19、如何解决地理信息路由算法中的局部优化和空旷域问题，路由空洞，右手法则，边界转发，贪婪策略；
·存在x到D的路径 ·x的邻居w, y离D的距离比x大
· D与X间距离为半径的圆与X的一跳传输范围发生重叠，且重叠区域内没有X的邻居节
点，称该重叠区域为X的空旷区域。
F是最佳主机 解决方法：边界转发 Perimeters Forwarding
边界转发时的右手法则(如右上图) ·一个数据分组从节点y到达节点x； ·下一条边的选择：
下一边是以x为定点，沿(x，y)逆时针方向上的第一条边，图中为(x，z) ·后续各边同样依次法则确定；
边界转发
·数据包在x点进入边界转发模式，通过face边界向目的节点D转发，这些face都被xD穿越；
·转发边的选择采用右手法则，初始边为xD； ·数据包在同一个face中转发时采用右手法则，当碰到与xD相交的边时，进行face切换，进入下一个face；
常用的贪婪策略
·MFR (Most Forward within Radius)：使到目的节点的跳数最少
·NFP (Nearest with Forward Progress)： 选择最近的邻居节点，使节点之间干扰最少 ·CR (Compass Routing) ：减小数据传输范围
局部优化问题的解决
·选择一个邻居节点使数据分组距离目的节点的距离变大（GPSR属于这个方法）；
·建议丢弃该数据分组，由于WSN的网络拓扑是动态变化的，出现局部优化问题的时间也是短暂的，丢弃的数据分组可以用更高层的重传来恢复；
路由空洞问题
路由空洞：
·邻居节点传输代价都比本地节点大；
·选择邻居节点中代价最小的作为转发节点； ·修改本地节点的转发代价；
F(N,R)= F(Nmin,R)+C(N,Nmin) ，
C(N,Nmin)表示将数据包从N传送到Nmin的代价
22、 如何解决网络能量和负载均衡 提出的方法
汇聚节点移动
最优移动策略：Sink节点在网络外边界移动，左图为圆形网络模型，灰色区域是Sink节点移动区域。
B为Sink节点，Rm为其移动圆形轨迹半径，R为网络半径，最好Rm~R
路由方法
·Sink移动区节点数据：
数据沿着以O为中心的环转发，直到该数据包到达OB(B为节点Sink所在的位置)线附近的一个节点，到达该节点后再沿着OB，采用最短路径算法到达Sink节点 ·Sink移动区外节点数据直接采用最短路径路由算法到达Sink节点 优点：
提出了一种新思路，通过Sink移动的方式从一定程度上削弱了网络中能耗和负载不平衡的现象 缺点：·大多数应用背景下要求Sink节点固定；
·普通节点定位Sink节点的问题不能很好的解决；
23、隐藏终端和暴露终端，产生的原因，如何解决
·隐藏终端是指在接收接点的覆盖范围内而在发送节点的覆盖范围外的节点。 （降低了信道的利用率）隐藏终端又可以分为隐发送终端和隐接收终端两种。 ·暴露终端是指在发送节点的覆盖范围内而在接收节点的覆盖范围外的节点。 （引入了不必要的时延）
·隐藏终端和暴露终端问题产生的原因
（1）网络具有动态变化的网络拓扑结构；
（2）在无线环境中，采用异步通信技术，各个移动节点共享同一个通信信道，存在信道分配和竞争问题；
（3）为了提高信道利用率，移动节点接收的频率和发射功率都比较低； 信号受无线信道中的噪声、信道衰落和障碍物的影响；
（4）因此移动节点的通信距离受到限制，一个节点发出的 信号，网络中的其它节点不一定都能收到，从而会出现“隐藏终端”和“暴露终端”问题。 ·隐藏终端和暴露终端问题的解决方法
解决方法的思路：使接收节点周围的邻居节点都能了解到它正在进行接收；
一种是接收节点在接收的同时发送忙音来通知邻居节点，即BTMA（Busy-Tone Multiple Access ）系列；
另一种方法是发送节点在数据发送前与接收节点进行一次短控制消息握手交换，以短消息的方式通知邻居节点它即将进行接收，即RTS/CTS方式。这种方式是目前解决这个问题的主要趋势，如已经提出来的CSMA/CA、MACAW等。还有将两种方法结合起来使用的多址协议，如DBTMA。
对于隐藏发送终端问题，可以使用控制分组进行握手的方法加以解决。
在单信道条件下使用控制分组的方法只能解决隐发送终端，无法解决隐藏接收终端和暴露终端问题。
为此，必须采用双信道的方法：即利用数据信道收发数据，利用控制信道收发控制信号。
24、 MAC协议的分类方式
（1）分配信道的方式：竞争型、
分配型、混合型
（2）使用的信道数目：单信道、双信道、多信道
（3）网络类型：同步网络、异步网络
25、 CSMA/CD和CSMA/CA的主要差别
CSMA/CD：带有冲突检测的载波监听多路访问，可以检测冲突，但无法“避免”：
CSMA/CA：带有冲突避免的载波侦听多路访问，发送包的同时不能检测到信道上有无冲突，只能尽量‘避免’；
1.两者的传输介质不同，CSMA/CD用于总线式以太网，而CSMA/CA则用于无线局域网802.11a/b/g/n等等；
2.检测方式不同，CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；而CSMA/CA采用能量检测(ED)、载波检测(CS)和能量载波混合检测三种检测信道空闲的方式；
26、 如何解决MAC协议中传感器节点的早睡问题
早睡问题的定义: 节点在邻居准备向其发送数据时进入了睡眠状态 早睡问题解决办法
（1）未来请求发送（Future request-to-send, FRTS），包括节点接收数据前需要等待的时间长度。C发送的FRTS可能干扰A发送的数据，所以A延迟发送数据，接收到CTS后发送一个与FRTS相同的DS (Data-Send)帧，不包含有用信息，为了保持AB对信道的占用。 FRTS可以提高吞吐量，减少延迟，但是增加了控制开销，降低TMAC协议的能量效率。
（2）满缓冲区优先（Full-buffer priority）：当节点的缓冲区接近占满时，对接收到的RTS帧不回复CTS，而是立即向缓冲区中数据包的目的地址发送RTS，以建立数据传输。优点是减少了早睡问题发生的可能性，在一定程度上能够控制网络的流量。缺点是在网络数据量较大时增加了冲突的可能。 AContendRTSCTSACKDATAAContendAContendRTSCTSACKDATA
BBBContend
ContendContendC Contend Contend C Contend CRTS DActiveSleepDDActive ActiveDATARTSCTSACKFRTSRTSRTS?TATATA
早睡问题 FRTS帧交换 接受RTS节点优先
