基于多点中继的CDS技术优化

一些骨干网方案基于节点S的多点中继（Multi-point Relay，MPR）概念，它定义为所有给定节点S的最小尺寸子集，该子集将覆盖节点S的所有两跳邻居。它要求每个节点收集两跳知识。如果节点A是节点B的直接（单跳）邻居，则称A被B所覆盖。S的中继节点都是S的单跳邻居，它们覆盖了S的所有两跳邻居。目标是最大限度地降低S中继节点的数量。具有最小尺寸的MPR集计算是一种NP完全问题（Qayyum et al.，2002）。在CDS构建过程中，可以通过使用Guha-Khuller算法来确定中继节点数，这仅限于给定节点的两跳邻域。它与参考文献（Lovasz，1975）中提出的一种称为贪婪覆盖集算法的启发式算法类似。该算法重复选择节点B，以确保未被覆盖的邻居节点数最大化。在图2-9a所示的实例中，灰色节点2、5、6是节点0的中继节点，且尺寸是最小的。

图2-9 MPR-CDS算法

a）节点0的中继节点2、5、6 b）参考文献（Adjih et al.，2005）给出的MPR-CDS节点{a，b，f，g，h}和参考文献（Wu，2003）给出的MPR-CDS节点{a，f，g，h}(www.xing528.com)

参考文献（Adjih et al.，2005）提出了一种基于MPR的、用于CDS骨干网构建的算法（MPR-CDS）。每个节点通过选择单跳邻居的一个子集，来计算该节点的MPR集。这些单跳邻居覆盖了所有的两跳邻居。节点将中继列表添加到“问候”消息中，“问候”消息将以广播的形式发送给节点的邻居。中间节点收到“问候”消息后，如果该节点在其区域中拥有最小的ID或它是拥有最小ID的邻居的MPR，则该中间节点将加入到CDS中。参考文献（Wu，2003）通过去除邻居中具有最小ID、但不存在两个非连通邻居的节点，对该规则进行了改进。构建MPR-CDS骨干网需要用到两跳邻居知识，加上包含每个节点的中继节点列表的消息。总体来看，CDS构建需要用到三轮消息，如果CDS决策需要传送给邻居，则需要四轮消息。

考虑图2-9b中所示的实例。在节点a和b的邻居中，由于它们具有最小的ID，因而它们决定加入到CDS中。节点a计算其MPR集{g，h}，然后将该列表添加到其“问候”消息中。当节点g和节点h收到“问候”消息后，它们也决定加入到CDS中。同样，节点f决定加入到CDS中，由于它是节点b的MPR。最后，根据参考文献（Adjih et al.，2005）提出的算法，节点{a，b，f，g，h}形成一个CDS。通过使用参考文献（Wu，2003）提出的算法，CDS并未选择节点b，因而CDS集为{a，f，g，h}。