基于剩余能量等级的MANET分簇算法

2018-10-18，，

计算机测量与控制 2018年10期

，，

(1.中国电子科技集团公司第五十四研究所，石家庄 050081；2.中国人民解放军第96764部队，河南洛阳 471000)

0 引言

移动自组织网络(Mobile Ad Hoc Network，MANET)是一种无需依赖固有通信基础设备的网络，它不仅能够实现快速组网，还能够通过无线终端的相互协作实现信息传输与维护。MANET具有自组织性、拓扑动态性、多跳通信和分布式控制等特点[1]，实用于军事战场、地震、水灾后等场合的紧急通信。MANET研究方向主要包括方面六个方面：定位技术、节能技术、信道接入技术、路由协议、网络体系结构和网络安全技术[2]。

MANET的网络结构分为平面结构和分级结构，分级结构比平面结构的可扩展性好，路由和控制开销也相对较小，更易于实现网络的移动性管理和局部同步[3]。目前研究的MANET分级结构是基于分簇实现的，如何设计简单高效的分簇算法来减少MANET的路由和计算开销，提高簇间通信效率是MANET研究的一个重要方向。典型分簇算法包括最小ID算法、最大连接度算法、最低移动性算法和加权分簇算法[4]。由于现有自组织网络设备采用手持或者背负的携带方式，能源通常会受到限制，然而传统算法没有考虑能量消耗的因素。为了实现节能延长网络寿命，节点剩余能量逐渐成为分簇算法考虑的重要因素。文献[5]提出了一种基于局部竞争和双权重通信能量开销的分簇算法，有效延长网络稳定工作寿命，提高网络节点能量使用效率。文献[6]分别建立能量和密度的影响因子，并加上不同的权重，让剩余能量多、密度大的节点当簇首，均衡网络能耗，有效延长网络寿命。文献[7]分别考虑了单跳和多跳网络，改进了现有的分簇算法，在均衡节点能耗的同时，提高网络的能效和延长网络寿命。

本文主要针对手持型自组织网络的节点能源受限、快速移动以及网络变化随机性强的特点，研究出一种基于节点剩余能量的分簇算法。根据节点位置信息进行自适应分簇，建立节点能量等级模型选取最优簇头，动态构造分级结构的自组织网络，从而达到延长网络生存时间和平衡簇头负载的目的。

1 MANET网络结构

MANET拓扑结构可分为平面结构和分级结构。图1(a)所示的为MANET的平面结构，网络中各个节点的功能和地位相等，网络结构具有较强的健壮性。但是由于在大规模组网和节点移动性强的网络中，平面结构网络的时延长、路由维护和管理开销大，随着网络节点数增加，吞吐量也会急剧下降，所以它只适用于移动性低的中小型网络。

MANET的分级结构如图1(b)所示，此结构是将网络中的所有节点进行分簇，将位置比较近的几个节点，按照某种算法合并成一个簇，从而将整个网络分成若干个簇。在每个簇中使用簇头对簇内的节点进行集中化管理。同时处于多个簇头节点覆盖范围内的节点叫做网关节点，或者跨簇节点[8]。分簇结构的优势是可扩展性好，网络规模不受限制，而且路由和控制开销较小，易于实现移动性管理和网络的局部同步；劣势是簇头节点消耗能量大，容易成为网络生存的瓶颈，而且分簇结构的安全性较差。

图1 MANET网络结构

1.1 簇头功能

簇头主要负责管理和维护簇结构与节点信息，转发簇成员之间的数据[9]。簇头是每个簇的管理者，一般用作网络的管理与调度。簇头可以预先设定，也可以根据预设的优先级自动产生。当簇内的节点同时处于多个簇头的覆盖范围内时，某一时刻只能属于一个簇。

1.2 性能评价

分簇算法的性能优劣可以从以下几个方面做出评价。

1.1.1 簇个数

MANET中的簇个数较多或者较少时，分簇算法性能都会下将。簇个数多会增加端到端时延，簇个数少会导致簇内平均普通节点数目增多，吞吐率下降。

1.1.2 稳定性

MANET中节点的移动会导致簇中节点的离开与新节点的加入，从而会引起簇结构的变化。可以通过增强簇结构的稳定性，使分簇算法性能更好。

1.1.3 负载均衡度

簇头因为要维护簇的拓扑结构，能量消耗会远远大于簇其它节点。通过式(1)计算LBF值得到簇首的负载均衡度[10]。

(1)

式中，n表示簇首的数目，xi表示簇首节点i的成员节点数，u表示所有簇首节点的平均成员节点数，N表示网络中所有节点数目，LBF值是xi到xn方差的倒数，LBF值越大说明分簇算法的负载越均衡。

1.1.4 节能能力

MANET要充分利用现有的能源，降低簇的能量消耗，延长网络的生存时间。

2 MANET节点能量等级模型

为实现对节点剩余能量的评估，建立能量级别评估模型。设节点i接收数据功率为P1，发送数据功率为P2；接收数据分组时长为T1，发送数据分组时长为T2；接收数据分组包长为L1，发送数据分组包长L2；数据接收速率为V1，数据发送速率为V2，则可以将节点消耗能量Ei用以下的计算公式[11]表示：

Ei=P1T1+P2T2=P1L1/V1+P2L2/V2

(2)

当初始能量为E0时，则节点的剩余能量表示为：

Er=E0-Ei

(3)

由于簇首节点比普通节点消耗的能量要高，因此每轮要选择剩余能量相对较高的节点担当簇头。为衡量每个节点剩余能量在子网络中所有节点能量的相对水平，引入参量λ表示节点剩余能量的级别：

(4)

在上式(4)中，E(i,t)表示i节点第t次簇头选择时的剩余能量，Eave(t)表示簇内存活节点的平均能量。舍去λ<1的节点，将剩余的节点设为4个等级，如表1所示。

表1 剩余能量级别

3 MANET分簇设计

3.1 自适应分簇

自适应分簇过程是将整个网络监测区域内的所有节点按照一定原则，划分为若干个子区域，每个子区域中的节点组成一簇。自适应分簇过程可以根据设定的子区域的节点密度范围，不断调整每个子区域内节点规模，实现每个簇的均匀分布，避免部分节点的能量消耗过快。图2为某个监测区内节点的分布图，当单个子区域内节点密度过大时，可以通过细化方式组成新的簇，如图3所示。

图2 节点分布图

图3 区域细化

自适应分簇具体过程如下：第一步将监测区域分成4个相等的子区域，根据每个子区域内节点数，计算出LBF值；第二部开始细化节点数较多的子区域，设第t轮的子区域个数为Lt，第i个子区域内的节点数为Ni；每轮设定子区域内的节点数上限值Nmax，当Ni≥Nmax时将该区域一分为二，按照基数轮竖向分、偶数轮横向分的顺序依次从左到右，从上向下的顺序直至所有区域满足Ni≤Nmax。求出每次细化后的LBF值，选择最大时的分簇方法作为最终的分簇方案。

3.2 簇头选择

确定簇数目和各个簇的规模后，就需要进行簇头选择过程。以某个簇为例，首先根据剩余能量等级模型，计算出子区域内网络节点的剩余能量和平均剩余能量。通过比较各自的能量等级，选出具有最高等级的节点最为簇头。如果处于最高等级的节点不会是一个，需要再通过比较这些节点在子区域内到达最远节点的跳数，选取跳数最小的节点作为簇头，既可以保障网络的稳定性，同时又考虑了拓扑结构。

图4 簇头选择流程图

3.3 簇维护

簇头选择完成后，随着网络的运行，节点能量在不断消耗，需要定期对簇头进行维护。

图5 簇维护流程图

由于位置的移动，节点离开了原来簇头的覆盖区域进入其他簇头覆盖的区域，将重新发起簇头选择过程。如果是两个簇头节点移动到对方的覆盖区域时，具有较低能量等级的簇头将成为具有高能量簇头的节点成员。当通过对能量的计算，如果原簇头能量低于本轮最高节点剩余能量等级两级时，需要重新发起簇头选择过程。

此算法的优势为可以选择最优的簇个数，在保障簇内的吞吐量时，尽量减少端到端的时延。由于考虑了节点的剩余能量，能够避免个别节点过度消耗能量，平衡簇首节点的负载。在簇头剩余能量等级相差两级及以上时才进行簇头重选，适当避免了簇头的频繁更换，保障了网络的稳定性。

3.4 网关选择

当两个节点处于同一个簇时，可以通过簇头转发实现通信；属于不同簇时需要通过簇头和网关节点中继通信。网关节点选取的主要方向：保障跨簇通信时延的同时提高通信的稳定性。现有的网关选择方法包括随机算法、最大连接度算法、最小ID优先算法以及链路稳定优先算法等[12]，各有优势却难以避免节点移动引起的网关节点频繁更换。因此选择连接度大且运动范围较小的节点最为网关。

4 仿真计算与分析

Opnet仿真工具是一种网络仿真技术软件包，能够准确的分析复杂网络的性能，在1986年被首次创建后很快应用于各种领域[13]。本文采用Opnet网络仿真工具对设计的分簇算法进行仿真，并利用Matlab软件对其性能进行分析。

4.1 分簇过程

运用opnet软件，设定节点数目为40个，实验区域设定为10 km*10 km的方形区域，将40个节点随机分布在目标区域，如图6所示。

图6 节点分布图

首先将目标区域分成四个子区域，每个区域内的节点数目分别为12、8、6和14。根据自适应分簇过程，求出不同簇数目时的LBF值如表2所示。经过比较10个簇时LBF值最大，分簇性能最好。

表2 不同簇数的LBF值

当簇个数为10时，根据自适应分簇算法对目标区域的节点进行细化，得到40节点的各个簇中的节点数目。

4.2 端到端时延

影响网络时延性能的参数包括网络的规模、网络中的簇首节点个数、簇内成员节点的传输能力与传输范围、簇首节点的传输能力和传输范围、数据包的长度与数据包的到达率、节点的干扰模型和MAC层协议[14]。

运用opnet软件对网络进行仿真，网络中的节点分布如图7所示，设置传输功率为0.4 mW，节点数据包发送到达符合0.2秒的指数分布，数据包长度为1024字节，传输速率为1 Mbit/s。路由协议选择AODV协议，MAC层协议选择CSMA/CA协议。图8为总节点数为40个时，分别比较簇个数分别为6、8、10、12时端到端时延。由图8可知，当簇头数目为10个时端到端时延最小，同分簇过程得出的结果一致。