移动Ad Hoc网络中的常驻网管推举算法

admin

　　目前已有的Ad Hoc组网方式多为独立组网，即在同一网络中的各节点彼此通信，而不能与其他同构或异构网络中的节点进行信息的交互。为了适应不同应用场合的需要，两个使用不同路由协议的Ad Hoc网络在逐渐靠近的过程中，通过感知对方，自适应地进行网络融合，最终将两个网络统一切换为使用同一个网络协议的单一网络。其过程是一个复杂的过程：两个网络能够相互感知；使用的路由协议需要统一；最重要的是节点的IP地址需要重新分配，以防IP冲突。而IP的统一分配需要一个网管来进行管理，在无线自组织网络中有—个特殊的节点，即常驻网管节点，它负责网络信息的统计及IP地址的发放。谁来担任常驻网管以及怎么选择常驻网管是我们需要深入研究的问题。作为常驻网管的节点需要具有以下特性：地理位置优越，最好位于网络的中心；有最大的连通性；常驻网管各方面的硬件性能比较稳定。

　　1 分簇算法

　　目前的分簇算法有：对节点ID进行排序的最小ID启发式算法；基于节点度数的最高节点度数算法；折衷考虑各方面的加权组合簇算法。

　　最小ID启发式算法由Baker和Ephremides最早提出，也称为基于识别器(identifier-based)的分簇算法。这种算法中每个节点都具有唯一的序列号(ID)，序列号最小的节点被选择作为簇头，因而每个簇内一般节点的序列号要大于簇头的序列号。位于两个或多个簇内的节点称为网关，对于不相互覆盖的两个簇，可以定义两个分别位于不同簇内的节点作为分布式网关；节点与网关(或分布式网关)之间的联机构成一个支配集，即整个骨干网，从而保证所有节点之间的通信。

　　该算法计算量小，实现方便，算法收敛较快。该算法的簇头更新的频率较慢，维护簇所需花费的开销较小，并且位于簇和簇内节点的数目较为合理，网络的吞吐量高于最大连通度算法。但它也有一些缺陷，由于该算法倾向于选择具有较小ID的节点作为簇头因而所选择的簇头也相对固定，这使得这些簇头节点消耗更多的电池能量，在一定时间后将无法继续工作，缩短了整个网络的生存时间，同时该算法也没有考虑负载平衡等因素。

　　最高节点度数算法由Gerla和Parekh最早提出，也称为基于连通度的分簇算法。其中节点的连通度由它与周围节点的距离来确定。每个节点在其发射范围内向周围节点广播唯一序列号(ID)，若它与周围节点的距离小于发射范围(与一定的发射功率相对应)，则它们是邻居节点。—个节点的邻居节点的个数称为它的连通度。具有最大连通度的节点被选择作为簇头，其周围邻居节点作为该簇内的一般节点，只能与簇头进行通信。该算法借鉴了Internet中选择路由器的方法，尽量减少路由器的数目，因此该算法的目标是产生尽可能少的簇数。节点之间通过交互控制消息了解其邻居节点的数目，该节点和其相邻节点中具有最大度的节点被选为簇头(当度数相同时则选择ID最小的节点作为簇头)，簇头的一跳邻居节点则成为该簇的普通成员节点，反复进行以上过程直到所有节点都加人某个簇。

　　该算法的优点在于簇的数目较少，减少了网络的平均时延。但由于簇的数目较少，信道的空间重用率较低。该算法对簇内的节点数不加以限制，当簇内节点数量过多时，由于簇头节点的处理能力有限，必然导致数据包的丢失、时延增加以及吞吐量的急剧下降。此外，当节点移动性较强时，簇头的更新频率急剧上升，这是最大连通度数算法固有的缺陷。

　　加权组合簇算法：Basagni等人最早提出两种节点加权算法：分布式分簇算法DCA(distributedclustering algorithm)和分布式移动自适应分簇算法DMAC(distributed mobility-adaptive clusteringalgorithm)。其中每个节点根据其成为簇头的适合程度分配一个权值(大于零的实数)，该节点和邻居节点中权值最高的节点被选择作为簇头，而其相邻节点作为簇内一般节点。如果权值相同，则选择ID较小的节点作为簇头。DCA算法假设执行过程中网络拓扑稳定不变；而DMAC算法则相反，适合于任何移动网络情况。

最高节点度数算法简单，将作为我们的一种候选方式，但它没有考虑邻居节点的相对位置以及邻居节点周围节点的分布情况，对节点周围拓扑结构考虑不完全。本文在最高节点度数算法的基础上，提出了1-hop相关密度算法和2-hop相关密度算法，尽量确保常驻网管节点位于网络的中心。

　　2 网络模型

　　无线网络可以简化为一个无向图G=(V，E)，∣V∣=n，表示移动节点的集合。当且仅当u和v相互在传输范围的时候，称u和v为邻居节点，边(u，v)属于E。

　　2.1 算法相关定义

　　定义1：邻居节点的相关度。设T为节点给传播范围最边缘上的节点发送HELLO信息，且收到应答时的时间差。T为一个近似值，主要与节点的无限传播范围有关。t(u，v)=tvu-tus，tus示节点u向邻居节点广播HELLO消息的时间，tvs表示u收到v应答　的时间，t(u，v)表示消息传播的时间差，反映了u和v两个点之间的距离。节点v对u的相关度定义为。u和v的距离越小，t(u，v)越小，相关度就越大；当u和v两点重合时相关度最大，而当v在u的无限传播范围的边缘时相关度最小。
　　定义2：节点l-hop内节点相关密度。设u的邻居节点集S={v1，v2…vn)，则u一跳内相关密度定义为。
　　定义3：节点2-hop内节点相关密度。设u的邻居节点集S={v1，v2…vn}，则u两跳内相关密度定义为。

　　v1、v2、v3三点都是u的邻居节点，每个节点分别算出自己的1-hop相关密度后再发给u点，u根据邻居节点的1-hop相关密度计算自己的2-hop叩相关密度。不同节点的邻居节点可能重合，有些节点可能以不同的方式计算多遍，我们为了简便不多加考虑，只是进行简单的相加。

　　2.2 最大2-hop相关密度算法

　　此算法将在每个节点上运行，每隔一定的时间周期执行一次。过程为：初始化，每个节点的1-hop相关密度和2-hop相关密度都设为0。周期广播HELLO消息，存储广播时间，以便与收到的应答时间作比较，启动定时器等待应答；邻居节点收到HELLO消息后回复应答；收到所有邻居节点的应答后(指未超时的应答)，计算邻居节点相对自己的1-hop相关密度，采用定时器超时的方式，在定时门限内收到应答的节点认为是邻居节点，更新自己的邻居列表；广播自己的1-hop相关密度(由事件触发，计算出1-hop相关密度后即发布)；接收到所有邻居节点的1-hop相关密度后，计算自己的2-hop相关密度，如果自己的最大2-hop相关密度表为空，则把自己的相关密度直接存人。如果不为空则进行比较，若比已存的大，则向邻居节点广播自己的2-hop相关密度，再替代原有的相关密度；否则不作操作；邻居节点收到2-hop相关密度后，即与自己已存的最大2-hop相关密度表(本节点或其他节点的)作比较，如果比已存的大，则用该节点及2-hop相关密度替代原来的最大2-hop相关密度，再向邻居广播，否则不做操作；在设定时间周期后，所有节点检查最大2-hop,相关密度对应的节点是否是自己，如果是则是常驻网管节点，开始发布网管信息。

　　2.3 2-hop相关密度算法的优缺点

　　2-hop卡目关密度算法是在1-hop相关密度算法基础上实现的，节点首先计算出1-hop相关密度，再根据邻居节点的1-hop相关密度计算2-hop相关密度。因此2-hop相关密度算法综合考虑了节点2-hop内的节点分布情况、节点的连通性及节点的距离关系。采用这种相关密度算法使得选出的常驻网管节点具有最大的连通性，而且位于节点密集区，更有利于在无线自组网中进行统一地管理。但是2-hop相关密度算法是基于消息的，度数的传递也由消息来完成，最大2-hop相关密度使得消息在—个节点上要传递两次，同时消息又是基于全网广播的，会造成一定的网络开销，所以该算法是在容忍推举开销的基础上实现的。

　　3 仿真分析

　　仿真场景：在100*100的范围内随机布点，每个点的覆盖范围是30米。根据3种算法选出相对应的网管节点，计算网管节点到网络内所有节点的平均距离，比较3种算法选出的网管的优劣。

　　首先我们引入网络中点的概念，平均最短径长最小的端为网的中点，它是到各节点的平均转接次数最小的点。我们定义的中点是到网内各节点的平均距离最小的点，Si为节点i到所有节点的距离和。，di是最小的平均距离，对应的i*为网的中点。所以我们只要计算出每种算法选出的节点到网中所有其他节点的平均距离就可以判断选出的网管节点的好坏。

　　图2中横坐标为仿真的次数，对应的纵坐标为相同场景下3种算法计算出来的网管节点到网内所有节点的平均度数。最高度数算法和1-hop相关密度算法得出来的平均距离波动比较大，第3、5、6、15次仿真计算出的值都高出很多，可见计算出的节点不适合作网管。从总体分布来看，2-hop相关密度算法计算出的值明显比另外两种偏低，因为2-hop相关密度算法考虑了两跳内的节点的位置关系及整网的密集度。由此可见采用2-hop相关密度算法选出的节点更适合充当网管。

　　但从控制开销和复杂度分析，2-hop相关密度算法为了测试两点间的距离，采用hello的应答机制，增加了控制开销；2-hop相关密度算法在计算出1-hop相关密度后还要进行广播计算2-hop相关密度，然后再广播2-hop相关密度进行比较，这些消息的处理与开销都增加了网络的负担及推举过程的复杂度。最高节点度数算法最简单，而且控制开销要少很多，不需要hello的应答机制，只需要广播一次节点的度数。1-hop相关密度算法的开销和复杂度介于上面两者之间，选出的节点到整网所有节点的平均距离的波动与最高度数法类似。表1对几种算法进行了比较。

　　4 结论

　　2-hop相关密度算法在选取网管方面确实有其优势所在，但本身的开销和复杂度难以忽略，如果在无线自组网节点上安装定位装置，如GPS，就可以很大程度上减少消息的交互，直接根据位置信息计算节点的2-hop相关密度，取2-hop相关密度最大的节点为网管。