DISTANCE(B，D)<DISTANCE(M，D)……(3)
 因此我们可以在ITGR发现信标节点的路径上逆向寻找第一个DISTANCE(X，Y)的峰值，并将其称为新信标节点。当知道更新过信标节点后，下次S点再发送数据包到D时，直接将数据包发送给B2，然后由B2转发给D点。从图1中可见，未更新信标节点前，数据包发送路径为实线代表的路径，共16跳；更新过信标节点后，数据包发送的路径为虚线所代表的路径，共12跳。可见更新过信标节点后，可以节省路由跳数。采用ITGR算法，S点第二次向D点发送数据时，先将数据发送给间接目标节点B1点，但在使用贪婪算法向B1点发送数据的时候，到达Z点遇到空洞问题，此时Z点使用周边模式向B1转发数据包。而如果采用了更新信标算法，S点第二次向D点发送数据的时候直接将数据包发送给B2，此时，路由路径不需要进入周边算法模式，从S到B2和B2到D点都可以直接使用贪婪算法转发。

    假设X为射线SB2上的一点，Y为射线SB1上的一点，Z为射线SP上的一点。则ITGR算法中目标节点阴影区域为YB2PZ，如图2中的斜线区域；更新信标节点后，目标节点阴影区域为XB2PZ，如图中的网状区域。由图2可见区域XB2PZ比区域YB2PZ更大，说明采用新信标节点可以扩大目标节点阴影区域范围。

    改进后的路由算法描述如下：源节点向目标节点发送数据时，按照ITGR算法将数据包转发到B1点，在B1点按照ITGR算法数据发送模式由周边算法模式恢复到贪婪算法模式中。我们在此加入LBD(landmark backward discovery)算法，即信标节点后向推移算法。根据ITGR算法，路由模式mode在B1点将变为GREEDY，此时节点将采用LBD算法转发数据，算法伪代码如表1所示。LBD首先判断信标节点的上一跳节点是否比信标节点到目标节点的距离更远。如果不是，则直接继续按ITGR原来算法运行；如果是，则更改数据包模式并将数据包发送给上一跳节点，然后按照左手法则依次向回查找距离目标节点，直到查找到新的信标节点或者回传数据包到局部最小节点。
3 仿真结果
    本文使用离散仿真器OMNeT++4．0对ITGR算法和更新信标后的ITGR+LBD算法进行仿真对比。整个实验网络为1500m×2000m，网络内随机分布200到400个节点，每次仿真增加50个节点，节点保持静止状态，网络中间存在一个900m×200m的空洞，空洞上方的一个源节点向空洞下方的10个目标节点各发送10次数据。

    仿真主要测量平均路由跳数和路由路径平均长度，仿真结果如图3和图4所示。由图3可见更新信标节点后，平均路由跳数最少减少9.4 6％，最多减少21．92％，平均减少15．18％。由图4可见，更新信标节点后，路由路径平均长度最少减少6．46％，路由路径平均长度最多减少15．72％，平均减少11．03％。采用ITGR算法第二次向目标节点发送数据的时候首先使用贪婪算法转发到信标节点。但当网络中存在窄带型空洞的时候，使用贪婪算法向信标节点转发数据有可能重新遇见空洞，造成迂回路径。而采用新的信标节点后，由于新的信标节点一般位于窄带型空洞的两端，所以有效地减少了向信标节点发送数据的时候重新遇见空洞的问题，缩短了路由路径长度。另外当后移了信标节点后扩大了目标节点阴影区域，使得更多的目标节点可以使用已发现的信标节点，避免了二次重复信标发现。仿真实验结果证明了采用新的信标节点后，可以降低路由路径的平均跳数和路由路径的长度。

4 结论
    本文提出一种ITGR的改进算法，通过逆着到目标节点的路由路径方向选择新的中信标节点，可以扩大ITGR算法中目标节点阴影区域范围，减少算法进入周边模式的次数，改进的算法既能有效地绕过空洞，又能有效地缩短绕空洞时路由路径的迂回长度。仿真实验表明，当网络中存在窄带型空洞时，更新信标节点可以有效降低ITGR算法的路由跳数并缩短路由路径的长度。

上一页  [1] [2]