面向无线通信网络的分簇稳定性控制研究∗

付 蝶

（四川文理学院信息化建设与服务中心 达州 635000）

1 引言

移动无线Ad Hoc网络（MANET）［1］是由一组不依赖于固定通信网络设施的无线移动节点组成，能够快速形成网络体系并提供重要通信与服务的临时网络。MANET具有多跳路由，节点能量有限，无线通信环境不可靠，动态拓扑快速变化等特性［2］。为了提高MANET的可扩展性，分簇是一种十分重要与常见的策略。采用分簇策略［3］后绝大多数节点的信息交换次数会降低，因此节点路由信息维护开销也将降低，此外网络规模也可以在一定程度上得到增大，并可保证网络管理与控制的高效性。

分簇［4］的基本思想就是按照位置的远近关系将网络的节点分成若干集群，以便于管理。在一个簇内，部分节点负责建立分簇并且维持网络拓扑的稳定性，这样的节点也被称作簇首节点，簇首节点的集合构成一个支配集［5］。簇内的节点一般被划分为普通成员节点与协助簇间通信的网关节点，即簇首节点之间不进行直接的信息交换。一般的MANET分簇算法根据某些本地条件或者Ad Hoc网络的属性（例如节点密度、移动性、权重、剩余能量等因素）将节点加入到簇首节点集合之中［6］。现有的分簇机制中往往忽视了节点分布、节点频繁变动对分簇稳定性的影响，且以上工作虽考虑到多种参数对分簇的影响，但多采用观测值［7～9］的方法，缺乏严谨的推导模型来进行簇首选择判定。因此本文有必要设计新的理论化簇首选择判定模型。

此外，现有的分簇算法中未考虑如何维护调整动态网络环境下的分簇结构。因此，本文还需给出相应的分簇维护机制以保证分簇结构的调整。本文的主要贡献在于以下三个方面:1）提出了簇的期望生存时间模型，保证分簇在动态环境下具备更高的稳定性，即提高了簇的生存时间。2）给出了簇的可靠性通信度量模型，提高了动态环境下的通信可靠性，并降低了成员节点与簇首节点的更新次数与随之带来的通信开销。3）给出了分簇的维护机制，以保证分簇结构的有效调整。

2 Ad Hoc网络模型

根据图论［10］知识可知，平面Ad Hoc网络可以用一张无向图来表示，即G=(V,E)。其中V代表了节点vi的集合，E表示由所有链路ei组成的集合。一般情况下节点的个数恒定，即V的势保持不变，但E的势随着链路的建立和删除发生改变。因此也可将分簇称作受到额外限制的图形分割问题。由于基本图没有表现出任何规则形结构，所以根据一定参数对图形进行分割就成为一个NP-Hard问题［11］。分簇策略主要关心的问题是如何寻找支配集即最佳簇首集合:，使得成立。其中 N[vi]表示节点vi的相邻区域，可定义为

其中，txrange表示节点vi的传输距离，通常情况下所有节点的传输半径大小一致。节点领域密度被定义为N[vi]的势，即

3 簇首的稳定性度量模型

短暂的成簇时间会导致簇首节点与成员节点的频繁更迭，随之带来的通信开销会增大节点的计算压力，此外簇内节点分布对通信质量的影响亦会对簇的稳定性产生很大的影响。考虑到以上问题并未在以往文献中得到很好的解决，本文设计了簇首的稳定性度量模型。该模型有以下两个优点:1）保证所选择的簇首节点所构成的簇具有最佳的生存时间；2）保证了所划分簇的节点分布产生较小的通信开销，同时具备较好的通信可靠性。

3.1 簇的期望生存时间度量模型

位于同一个分簇内的节点由于节点地位的划分被分成簇首节点与成员节点。从拓扑稳定的角度出发，作为簇首的节点“希望”其成员节点位于簇内的时间越长越好，而成员节点亦“希望”其共同的簇首节点作为簇首的时间越长越好。簇首节点与其成员节点位于同一簇内的时间越长说明节点的变动频度越小，即提高了簇的稳定性，同时降低了节点频繁变动带来的通信开销。单纯的移动性衡量方式并不能保证簇内节点位于同簇的时间较长，而以往的簇结构稳态度量方式也缺乏严格推导。为此，本文将簇的期望生存时间值，即簇首节点与其成员节点位于同一簇内的期望时间值作为衡量簇的稳定性的指标之一，并给出相应的推导公式。

假设在MANET，所有节点都含有GPS模块，且节点的传输半径都表示为R，则可得出簇首节点i与其任一成员节点 j在同一簇的生存时间求解方程:

其中，v表示节点速度，Dij表示节点之间的距离值，Dxij与Dyij分别表示该距离在水平与竖直方向的分量。此外

因此簇的期望生存时间被定义为

其中，dist()表示节点之间的距离函数，ni为成员节点个数。概率函数Pij表示节点i为簇首节点时，节点 j为其成员节点且两点的距离值恰为Dij的概率。根据概率函数的定义，首先需要推出节点j位于节点i的传输半径范围之内的概率分布函数表达式 p{dist(i,j)≤R}。根据本文对网络场景设定，节点的平面分布概率密度函数可表示为

其中，L表示场景的长度，W表示场景宽度。考虑到节点与节点之间具有相互独立性，两个节点的联合平面分布概率密度函数就可以记作:

至此可以得出节点 j位于备选簇首节点i的传输半径范围之内的概率分布函数:

其中，元积分函数 funit_PDF(dist)为分段函数，当0＜R＜W 时，

当W≤R＜L时，

将式（12）带入式（5）就可推导出 E(Ti)的量化度量函数。

通过求解簇的期望生存时间可知，若簇结构稳定性较高，则簇首节点所在的簇具有较大的E(Ti)值。除了规避以往分簇算法中采用移动性测度的缺陷，E(Ti)测度函数能较精确地衡量成员节点在簇中的权重大小(Pij)，即考虑到成员节点分布差异对簇结构稳定性的影响。在本文中，E(Ti)将作为新的簇首选择测度因子之一。

3.2 簇的可靠性通信度量模型

在簇首节点传输覆盖的范围之内，成员节点距离簇首节点越近通信质量越好，反之信号随着距离的增大而迅速衰减，成员节点与簇首节点的通信越发困难［13］。现有分簇算法大多将簇首节点与其成员节点的距离之和作为通信开销度量因子，距离之和越小表明节点作为簇首节点的距离属性、通信属性越好。而在实际网络中，往往存在簇首节点与其成员节点距离之和相同，而成员节点分布各异的情况。若在此情况下，节点分布差异会导致簇的整体通信质量与通信开销的不同，则以往关于簇首选择的策略缺乏完备的考虑。通信质量与报文丢失率存在负相关且报文丢失率Ploss与距离的函数关系可表示为［14］

式中，a,b,c,d为大于0的正拟合系数，x为节点之间的距离大小值，erf()为标准误差函数。为了反映节点分布对通信质量的具体影响，对Ploss(x)求一阶导数可得:

基于上述推导，本文可对簇的结构进行分层处理，图1所示，并做出如下合理假设:当成员节点处在(0,r]时，簇首节点与成员节点的通信质量处在可接受范围内即不产生通信风险；反之，当成员节点处在(r,R]时通信质量发生快速衰减，产生通信风险。

图1 簇的分层结构

图2 节点分布对通信的影响

图2 给出了此时簇成员节点分布不同导致通信质量不同的示例。如图2所示，A、F分别为簇的簇首节点，距离簇首节点F距离之和分别为

若DA=DF，则以A为簇首的四个成员节点全部落入通信质量可接受的区域范围内，而以F为簇首的簇的四个成员节点中有2个节点落入通信质量快速衰减的区域范围内。此时两个簇虽然具有相同的距离属性与密度属性测度，却产生不同的通信属性测度。

为了形式化的描述此时节点分布不同对通信质量产生的影响，本文将通信风险概率分布函数定义为

其中，i表示簇首节点，j表示其成员节点，λ是一个介于0与1之间的调节系数。由此簇首节点i的平均通信风险代价（Communication risk）函数可被定义为

其中，n1表示距离簇首节点为(0,r]区域范围内的成员节点数，ni为节点i的成员节点数。

考虑到MANET作为一种具备局部连通性的特殊聚集网络［15］，本文对聚集网络的标准中心性指标［16］函数进行改进，并作为MANET簇首通信负载（Communication load）函数以反映节点作为簇首的通信开销与负载能力:

至此，可将簇的可靠性通信度量函数定义为

其中，Rci的取值越大，节点i作为簇首节点所在簇的通信开销越小，簇的平均通信质量越高；反之，Rci越小则簇的通信开销越大，簇的平均通信质量越低。因此在考虑节点通信质量与可靠性的同时，Rci仍反映了备选节点的距离测度与密度测度对簇首选择的影响。

为了维护簇结构的稳定性，簇首节点所在簇应该具备较高的期望生存时间与通信质量且产生相对小的通信开销。因此本文把簇首的稳定性度量函数即簇首选择函数定义为

其中，τ代表Ad Hoc网络系统所在的时刻，w1+w2=1，E'(Ti)和 Rc'i(τ)为归一化表达式可记作:

至此，本文给出基于稳定性度量模型的一次簇首节点选择算法过程:

算法1一次基于稳定性测度的簇首选择

输入:G=(V,E)

输出:簇首节点（Clusterheads）

Fo（r所有节点i）Do:

将该消息以广播的形式发送到节点传输半径内的所有邻居节点。

Fo（r所有处在节点i传输半径范围内的节点j）Do:

存储收到的Wi信息，将收到的所有加权值与自己的加权值进行比较

IF（Wi为最大值）Then

j被选为簇首节点，且将该消息以广播的形式发送到其传输半径范围内的邻居节点。

Else

j接收到具有最大权重值节点的簇首选择信息。

End

3.3 分簇的维护机制

MANET的实时动态性会导致簇首节点与成员节点不断发生变化更迭。因为有必要给出一种分簇的维护机制以保证分簇结构的有效调整。考虑节点的两种移动行为可知，节点在加入簇或者离开簇的时候都会导致簇结构的变化。当节点为簇首节点时，在它离开所在簇的时候需要通知簇内所有的成员节点，与此同时，需要在该簇内重新选择一个合适的簇首节点。当节点为成员节点时，在它离开所在簇时就需要通知该簇的簇首节点，并更新成员表。用如下的流程表示节点离开导致的分簇维护机制:

算法2.1分簇的维护机制（节点离开行为）

Fo（r所有移动节点i）Do:

IF（节点i是簇首节点）Then

节点i在其所在的簇内向成员节点广播一条信息（放弃簇首状态）。

节点i将其当前状态更新为未决定状态，且申请加入一个可加入的簇。

Fo（r所有节点j，j是i所在簇的成员节点）Do:

节点 j更新所在簇信息并调用算法1重新选择该簇的簇首节点。

Else

IF（节点i是成员节点）Then

节点i向其所在簇的簇首节点发送一条信息（离开所在簇）。

节点i将其当前状态更新为未决定状态，且申请加入一个可加入的簇。

For（所有节点 j，j是i所在簇的簇首节点）Do:

节点 j更新所在簇信息并向其他成员节点广播一条信息（成员节点i离开簇）。

End

相应地，当成为未决定态的节点申请加入一个可加入的簇时，被加入簇的结构也会发生变化。用如下的流程表示节点加入簇导致的分簇维护机制。

算法2.2分簇的维护机制（节点加入行为）

For（所有移动节点i且节点i当前状态为未决定态）Do:

节点i发送一个广播信息申请加入一个可加入的簇，并等待可加入簇的回复信息。

IF（节点i收到了一条回复信息，即可加入的簇为1）Then

节点i加入该簇并更新相应的簇信息。

Else（节点i收到多条回复信息，即可加入的簇超过1）Then

节点i选择加入W值最大的簇并更新相应的簇信息。

End

至此，就给出了分簇的维护机制以保证在动态环境下分簇结构的有效调整。

4 本文提出的算法对比实验

4.1 仿真参数设置

本文利用NS-3［17］进行仿真实验，首先对实验参数进行配置，如表1所示。

表1 实验参数

本文的网络场景设为平面矩形场景，节点总个数以10作为递增单位，移动模型为random waypointmodel，节点的最大移动速度以5作为递增单位。

仿真实验将 WCA［18］、FCA［19］、TVCA［20］的分簇算法与本文提出的分簇策略（SCA）进行对比，比较它们在不同节点密度、动态强度（移动速度）下的相关性能。

4.2 平均簇首个数

图3描述了在Random Waypoint模型下，最大移动速度为10m/s，平均簇首节点个数与节点总个数的关系。从图中可知，平均簇首个数随着节点个数的增加而增大，但不具有严格的的线性关系。本文提出的算法（SCA）所得的平均簇首节点个数总体上多于WCA算法，少于其他两种算法（FCA＞TVCA）。不难发现FCA算法所得的平均簇首节点个数变动差异最大。用最大携带成员个数（2 ln(N)）衡量五种算法可知，本文提出的算法（SCA）与其余三种分簇算法都可保证成员节点个数小于最大携带成员个数。

图3 平均簇首节点个数vs节点个数

图4平均簇首节点个数vs移动速度

图4 描述了在Random Waypoint模型下，节点总个数为50，平均簇首节点个数与移动速度的关系。从图中可知，平均簇首个数不会随最大移动速度的增加而增大或减少，而是呈现一种小幅度浮动状态。本文算法（SCA）所得的平均簇首节点个数总体上多于WCA算法与FCA算法（FCA＞WCA），少于TVCA。

4.3 成员节点更新频度

图5描述了在Random Waypoint模型下，最大移动速度为10m/s，成员节点累积更新次数与节点总个数的关系。如图所示，成员节点累积更新次数会随着节点个数的增加而增大，但不具有严格的线性关系。在Random Waypoint模型中，本文提出算法（SCA）所得的成员节点累计更新次数最小。以本文提出的算法（SCA）作为基础进行对比，WCA、FCA、TVCA的成员节点累积更新次数平均增多了45.6%、8.1%、37.5%。

图5 成员节点更新频度vs节点个数

图6 描述了在Random Waypoint下，节点总个数为50，成员节点累积更新次数与移动速度的关系。如图所示，成员节点累积更新次数会随着最大移动速度的增加而增大，但不具有严格的线性关系。本文提出算法（SCA）所得的成员节点累计更新次数整体上最小。以本文提出的算法（SCA）作为基础进行对比，在Random waypoint模型中，WCA、FCA、TVCA的成员节点累积更新次数平均增多了60.1%、11.2%、33.6%。

图6 成员节点更新频度vs移动速度

4.4 支配集更新频度

图7 描述了在Random Waypoint模型下，最大移动速度为10m/s，簇首节点累积更新次数与节点个数的关系。如图所示，簇首节点累积更新次数会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法（SCA）作为基础进行对比，在Random waypoint模型中，WCA、FCA、TVCA的簇首节点累积更新次数平均增多了38.9%、18.3%、20.1%。

图7 支配集更新频度vs节点个数

图8 描述了在Random Waypoint模型下，节点总个数为50，簇首节点累积更新次数与移动速度的关系。如图所示，簇首节点累积更新次数会随着最大移动速度的增加而增大，但不具有严格的线性关系。以本文提出的算法（SCA）作为基础进行对比，在 Random waypoint模型中，WCA、FCA、TVCA的簇首节点累积更新次数平均增多了47.8%、15.2%、26.8%。

图8 支配集更新频度vs移动速度

4.5 节点通信负载

图9 描述了在Random waypoint模型下，最大移动速度为10m/s，单位时间平均每个节点发送信息数量与节点个数的关系。如图所示，单位时间平均每个节点发送信息数量会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法（SCA）作为基础进行对比，在Random waypoint模型中，WCA、FCA、TVCA的节点单位时间发送信息数量平均增多了35.0%、5.2%、23.9%。

图10描述了在Random waypoint模型下，节点总个数为50，单位时间平均每个节点发送信息数量与移动速度的关系。如图所示，单位时间平均每个节点发送信息数量会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法（SCA）作为基础进行对比，在Random waypoint模型中，WCA、FCA、TVCA的节点单位时间发送信息数量平均增多了44.6%、2.3%、21.8%。

图9 节点通信负载vs节点个数

图10 节点通信负载vs移动速度

4.6 结果分析

分析以上实验数据组，本文可得出如下的结论:

1）若用理想簇首节点个数（实现分簇全覆盖的最少簇首节点个数）衡量分簇效率，本文算法SCA得到的簇首个数指标并未获得最佳的分簇效率。

2）从支配集与成员节点更新频度的实验数据对比可知，本文提出的SCA算法能够有效地降低节点的更新频度，显著地提高了分簇结构的稳定性，这也说明了本文提出的簇首稳定性度量模型具有正确性。

3）簇首选择与频繁地节点更迭都会增加节点交换信息的数量，增加通信开销。从节点通信负载实验数据对比可知，本文提出算法（SCA）的通信负载指标优于其余算法，即有效地减少了系统的通信开销，也说明了本文提出的簇首稳态度量模型与分簇行为认知机制是实际可行的。

5 结语

分簇是一种提高动态网络可扩展性与拓扑稳定性的重要方法。现有MANET分簇算法中往往未考虑到节点分布差异与频繁的节点状态更迭对分簇稳定性的影响。基于以上事实，本文提出了基于稳定性控制的MANET分簇策略（SCA）。本文通过构建簇的期望生存时间模型与簇的可靠性通信度量模型，给出了一种新的簇首稳定性度量模型进行簇首选择。同样给出了分簇的维护机制，以保证动态网络环境下分簇结构的有效调整。实验结果证明本文提出的分簇算法能够有效地改善分簇的稳定性，并减少节点的通信负载。