邻居去除与基于骨干网的广播算法

参考文献（Stojmenovic et al.，2002）通过集成骨干网技术，进一步扩展了邻居去除方案。其框架基于两个概念：作为提供可靠性的特殊类型骨干网的CDS和邻居去除方案。CDS连通性提供穿越整个网络的传播，而CDS的支配性保证了网络中的所有节点都将是可达的。主要目标是在最大限度减少重传次数的前提下，提供可靠的广播。假定给定网络中已经构建了一个CDS骨干网。用于智能广播的通用算法（Stojmenovic et al.，2002）如下：假定源节点发送一条广播消息。节点首次接收到该消息后，如果节点不在CDS中，将不再对消息进行转播。如果该节点属于CDS成员，则它将基于若干个参数选择一个超时。在超时期间，节点可能会收到消息的多个拷贝。通过去除所有已经被这些消息拷贝覆盖的邻居，该节点更新其转发列表。当超时期满时，如果节点转发列表非空，则它将转播该消息。否则，取消重传。

图2-13 在邻居去除与基于骨干网的广播算法中，CDS节点G、E、F重传消息， 而节点H不重传消息

在如图2-13所示的实例中，假定节点S为源节点，且key=（degree，ID）。节点B、D、E、F、S、G、H、J和K包含两个非连通邻居。由于节点J的邻居被更高键值的节点H所覆盖，J不加入到CDS中。需要注意的是，节点B的邻居被具有较大键值的连通性节点E和F所覆盖。这样，节点B不加入到CDS中。同样，节点K的邻居被节点F和H所覆盖，节点D和节点S的邻居被节点E和G所覆盖。最后，节点E、F、G、H形成一个CDS。接收到来自于节点S的消息后，由于节点D拥有3个未被覆盖的邻居（即节点E、H和J），因而它将其超时设置为1/3。当超时到期时，节点G向其邻居重传消息。由于节点E不知道节点D被节点S覆盖，且它拥有4个未被覆盖的邻居A、B、D、F，因而节点E将其超时设置为1/4。节点H将其超时设置为1/2，因为它拥有2个未被覆盖的邻居F和K。然后，由于超时较短，因而节点E重传消息。重传之后，节点H将其超时更新为3/4（将初始超时调整为1，然后减去已经过去的1/4时间单元）。由于拥有3个未被覆盖的邻居C、I和K，因而节点F将其超时设置为1/3。由于节点F的超时比节点H的超时略短一些，因而节点F接着重传消息。之后，CDS节点H取消重传，所有节点接收到消息。(www.xing528.com)

需要注意的是，根据定义（Wu and Li，1999；Stojmenovic et al.，2002），CDS完全图是空集。但是，DS是重传消息的节点集，且在完全图的假设下，不需要重传消息（源节点发送消息后）。通常情况下，如果选择非空DS，则能够在其中添加具有最大键值的节点。也就是说，如果非中间节点的键值比其任一邻居的键值都大，则它可以添加到DS中去。由于采用了邻居去除（Stojmenovic et al.，2002），因而这对广播过程没有任何影响。

为了提高媒体接入控制（MAC）层的可靠性，Stojmenovic等人进一步引入了否定应答后重传（RANA）协议。当接收到第一条消息的初始部分（它包含了发送方消息）后，两条消息通常会发生碰撞。因此，接收方向发送方发送否定应答消息，请求进行重传。