控制与决策  2019, Vol. 34 Issue (6): 1271-1276  
0

引用本文 [复制中英文]

牛玉刚, 周振华. 带有重叠区域的多跳非均匀分簇路由算法[J]. 控制与决策, 2019, 34(6): 1271-1276.
[复制中文]
NIU Yu-gang, ZHOU Zhen-hua. Overlapping multi-hop unequal clustering algorithm[J]. Control and Decision, 2019, 34(6): 1271-1276. DOI: 10.13195/j.kzyjc.2017.1627.
[复制英文]

基金项目

国家自然科学基金项目(61673174);上海市优秀学术/技术带头人计划项目(16XD1421300)

作者简介

牛玉刚(1964-), 男, 教授, 博士生导师, 从事随机系统、网络控制系统等研究,E-mail: acniuyg@ecust.edu.cn;
周振华(1993-), 男, 硕士生, 从事无线传感器网络分簇协议的研究, E-mail:qdzhouzhenhua29@163.com

通讯作者

周振华, E-mail:qdzhouzhenhua29@163.com

文章历史

收稿日期:2017-12-01
修回日期:2018-01-26
带有重叠区域的多跳非均匀分簇路由算法
牛玉刚 , 周振华     
华东理工大学 化工过程先进控制和优化技术教育部重点实验室,上海 200237
摘要:能耗作为衡量无线传感器网络性能的一项重要指标, 通常将延长生命周期、均衡能耗作为网络协议重要的设计目标.针对静态、异构、非均匀分布的网络模型, 设计带有重叠区域的分簇及簇内单跳、簇间多跳的路由算法——OMU分簇路由算法, 该算法中簇头不再作为数据转发节点, 而主要用于簇内数据的接收与融合.通过综合考虑节点剩余能量、节点密度及与基站的距离进行簇头选举并进行分簇, 形成簇间重叠区域, 产生用于数据转发的中继节点.同时, 建立簇头与中继节点轮换机制以达到节点能耗均衡的目的, 并为每个节点建立能量最省的多跳数据传输路径.仿真结果表明, 所设计的分簇路由算法, 特别是在大规模部署的无线传感器网络中, 能有效减少和均衡能量消耗.
关键词无线传感器网络    非均匀分簇    重叠区域    多跳路由    生命周期    能耗均衡    
Overlapping multi-hop unequal clustering algorithm
NIU Yu-gang , ZHOU Zhen-hua     
Key Lab of Advanced Control and Optimization for Chemical Process, Ministry of Education, East China University of Science & Technology, Shanghai 200237, China
Abstract: As energy consumption is an important index to measure the performance of wireless sensor networks, prolonging lifetime and balancing energy consumption are important objectives during the design of network protocols. An overlapping multi-hop unequal clustering routing algorithm for static, heterogeneous and non-uniform network models is proposed. In this algorithm, the cluster head is no longer used as the data forwarding node, and is mainly responsible for the reception and fusion of data in the cluster. The residual energy, node density and the distance to the base station are considered for cluster head election and cluster formation. At the same time, overlapping areas between clusters are formed to generate relay nodes for data forwarding. The mechanism of cluster head and relay node rotation is established to ensure the balance of energy consumption. Moreover, a most energy-efficient multi-hop data transmission path is established for each node. The simulation results show that the clustering routing algorithm designed in this paper can effectively reduce and equalize the energy consumption, especially in large-scale wireless sensor networks.
Keywords: wireless sensor network    unequal clustering    overlapping areas    multi-hop routing    lifetime    energy balance    
0 引言

无线传感器网络是大量静止或移动的传感器节点以自组织和多跳的方式构成的无线网络, 目的是协作地探测、处理和传输感知对象的监测信息, 并报告给用户[1].不同于传统的无线Ad hoc网络, 无线传感器网络通常将能量消耗作为主要性能指标[2].

分层路由协议可以有效减少能量消耗[3].簇头节点负责接收簇内节点感知信息并进行融合, 去除冗余信息并进行转发, 可有效降低能耗, 减少网络中的通信冲突.近年来, 研究人员提出了很多分簇协议.文献[4]提出的低功耗自适应分簇协议(Low-energy adaptive clustering hierarchy, LEACH), 以轮为单位动态改变网络结构, 网络运行主要分为创建阶段和稳态阶段, 簇头接收簇内信息并融合, 再由簇头将数据直接发送给基站. LEACH协议能减少冗余信息的传输并显著降低网络能耗.但是, 由于LEACH协议设定簇头节点使用单跳的方式直接将数据发送给基站, 容易导致(特别是在较大范围部署的网络中)与基站距离较远的簇头消耗大量能量.同时, 以轮为单位的簇头轮换机制使簇头轮换过于频繁, 增加了网络中控制信息的传输.文献[5]提出了一种非均匀分簇路由算法(Unequal cluster-based routing, UCR), 确定了最大簇头竞争半径, 同时考虑了簇头与基站距离对簇半径的影响, 建立了越靠近基站簇半径越小的簇半径设定机制.但是UCR没有考虑随着网络运行, 节点剩余能量不同给簇半径确定带来的影响, 这会使网络的分簇不公平.文献[6]提出了一种基于负载均衡的分簇协议(DSBCA), 随机选择节点触发建簇过程, 由节点密度及与基站的距离共同确定簇半径大小.同时, 结合节点剩余能量、节点密度、成为簇头的次数这3个参数计算节点权重, 降低簇结构的改变频率.文献[7]引入了高能节点, 根据与普通节点的能量差异进行分簇, 但这种方式依赖于节点的部署, 没有高能节点分布的区域将发生能耗不均衡的现象.文献[8]中的基站位于圆心位置, 对此提出了一种等间距环形划分的分簇方法, 使同一环中簇半径相等, 越靠近基站, 簇半径越小, 但是这种方式没有考虑剩余能量及节点密度对簇半径的影响.文献[4-8]提出的协议中, 簇头既要负责簇内数据的接收与融合, 还要负责数据的转发, 这会导致网络中簇头节点能量消耗过快, 不利于网络能耗的均衡.文献[9]提出一种容错分簇算法, 通过粒子群优化负载均衡和能量消耗这两个目标, 有效地保证了网络的连通性并延长了网络生命周期, 但是, 它没有考虑网络中节点失效的问题.文献[10]提出了一种能量均衡前行路由的分布式非均匀分簇算法, 均衡了网络能耗并延长了网络生命周期, 但是其网络节点成为簇头节点之后角色便不再变化, 这不利于网络生命的进一步延长.针对这些问题, 文献[11]提出了一种多跳分簇算法(Distributed multihop clustering algorithm, KOCA), 选举出的簇头节点向k跳范围内的节点发送广播信息, 声明自己的簇头身份, 最终形成满足每个簇至少与一个其他簇存在重叠节点, 并能保证网络连通的簇结构.同时, 将簇头数据转发的功能交给中继节点进行, 降低簇头负担.然而, KOCA是一种静态簇结构, 没有考虑簇头轮换问题, 这将导致网络能耗的不均衡.文献[12]提出的EEOC(Energy-efficient overlapping clustering)协议通过两步形成了带有重叠部分的簇结构, 使用方向适应度函数形成重叠区域, 再选举隐藏高能量节点作为数据转发节点.但是, EEOC中簇头将数据发送给中继节点后, 中继节点直接将数据发送给基站, 这会增加网络能量消耗, 在大型网络中可能也无法实现.

本文提出一种带有重叠区域的非均匀分簇路由算法(Overlapping multi-hop unequal, OMU), 为每个符合条件的节点设定簇头竞争等待时间, 同时, 通过综合考虑节点剩余能量、节点密度以及与基站距离3个要素设定簇半径.建簇完成后, 为每个节点建立能耗最优的数据传输路径.数据传输时, 由重叠区域中的中继节点承担主要的数据转发任务.最后, 为了整个网络的负载均衡, 分别设定中继节点和簇头节点的轮换规则, 当剩余能量低于预先设定的阈值时, 才进行节点轮换.

1 系统模型 1.1 网络模型

本文假设共有N个传感器节点随机分布在M× M的正方形区域中.同时, 网络具有以下特性: 1)汇聚节点在监测区域之外, 所有节点都静止不动; 2)每个感知节点都有相同的初始能量, 汇聚节点没有能量限制; 3)每个感知节点都有唯一的节点编号且都是定位感知的; 4)感知节点周期性地发送感知信息; 5)节点之间的传输链路都是对称的, 每一对节点通信的功率能耗相同; 6)可以通过功率控制的方法来调整节点通讯范围.

1.2 能耗模型

本文采用文献[13]中简化的能量模型, 即

(1)

其中: ET(l, d)表示在距离为d的两个节点之间发送l bit数据所需要的能量, Eelec表示发射机和接收机处理l bit数据的功耗, εfsεmp分别是自由空间信道模型和多路径衰减信道模型信号放大器处理l bit数据单位距离的功耗, 表示区别自由空间信道模型和多路径衰减信道模型的阈值, ER = l Eelec表示接收l bit数据的功耗.

2 有重叠区域的多跳非均匀分簇路由算法

为了方便对算法的描述, 本文定义如下变量: Dmax为所有节点中与基站最远的距离, Dmin为所有节点中与基站最近的距离, rs为节点感知半径, wi为节点i簇头竞争参数, Erth为节点竞争成为簇头的剩余能量阈值, Eri为节点i的剩余能量, Nni为节点i的邻居节点个数, Di为节点i与基站的距离, Eravei为节点i所有邻节点平均剩余能量, Nravei为节点i所有邻节点平均邻节点个数, Twaiti为节点i竞争成为簇头的等待时间, rc为簇头竞争半径.

本文提出的OMU分簇路由算法主要包括5个阶段:信息采集、簇头选举、建簇、建立数据传输路由及节点轮换.

2.1 信息采集

在信息采集阶段, 主要完成对全局与局部信息的采集.每个节点向基站发送自己的坐标信息, 基站通过接收到的坐标信息计算出每个节点的距离信息, 并判断出与其距离最近和最远的节点, 将最近、最远距离分别记为DminDmax.每个节点在其感知范围rs内发送Hand_shaking信息, 包含节点号i, 剩余能量Eri和坐标信息(xi, yi).每个节点保存接收到的所有Hand_shaking信息, 接收到的信息条数即为此节点所有的邻节点个数.

2.2 簇头选举

在簇头选举阶段, 主要考虑了节点与基站的距离、剩余能量以及邻居节点个数3个因素.簇头节点不再作为主要的数据转发节点, 而是由选取的中继节点承担数据转发任务.显然, 越靠近基站的中继节点承担的数据转发任务越重.为保证网络负载的均衡, 越靠近基站, 每个簇需要越多的中继节点, 为满足此要求, 设定越靠近基站的簇拥有越大的簇半径, 以产生更多的中继节点.节点在竞争成为簇头时, 与其邻居节点比较剩余能量和邻居节点个数, 剩余能量越多的节点, 能够承担更多的数据接收与融合任务.成为簇头概率越大, 最终形成的簇半径也越大; 邻居节点越多, 表明该节点所处节点密度越大.为了负载均衡, 每个节点成为簇头的概率越大, 对应的簇半径越小.为了防止某些节点有较大的竞争参数wi而剩余能量过低的情况, 设定只有节点剩余能量大于阈值Erth时, 才能参与簇头竞争.综上, 可由式(2)计算出每个节点参与簇头竞争的竞争参数

(2)
(3)

再根据式(3), 由簇头竞争参数wi计算节点竞争成为簇头的等待时间Twaiti, δ为数据传输rc_max距离所需要的时间.每个参与簇头竞争的节点在自己的等待时间内如果没有收到从其他节点发送过来的簇头广播信息CH_ADV, 则成为簇头节点, 并在自己的簇头竞争半径rc范围内发送CH_ADV信息, 向此范围内的节点声明自己为其簇头.

若节点满足, 则网络以大于等于1-ε的概率连通[14].由此, 设定簇头竞争半径rc的最小值

(4)

为了减少网络通信能耗, 本文采用自由空间信道模型, 使簇内、簇间数据传输距离始终小于d0, 设定簇头竞争半径rc的最大值

(5)

簇的竞争半径rc由簇头与基站的距离、剩余能量以及邻节点个数3个指标共同决定.距离基站越远, 簇半径越小; 剩余能量越多, 簇半径越大; 邻居节点越多, 簇半径越小.由此可通过下式:

(6)
(7)

得出每个簇头的竞争半径(即簇半径)大小, 使其最大不超过rc_max, 最小值为rc_min.

2.3 成簇过程

本文设计了一种具有重叠区域的分簇协议, 一个节点可以同时属于多个簇.将簇与簇之间重叠的部分称为重叠区域, 并将在重叠区域的这些节点称为中继节点.簇头在通常情况下只负责簇内数据收集与融合, 数据转发主要通过中继节点进行.

在簇头竞争阶段选举出来的簇头在自己的竞争半径内发送CH_ADV信息, 每个普通节点不会拒绝接收到的CH_ADV信息, 将接收到的每一条CH_ ADV信息记录在CM_TABLE中, 并将最早接收到的CH_ADV簇头节点作为自己的主簇头节点, 用于接收自己的感知数据.若一个节点接收到多条CH_ ADV信息, 则说明此节点同时属于多个簇, 这些节点即中继节点.在接收到所有簇头的CH_ADV后, 簇成员节点向自己的主簇头节点发送加入请求信息JREQ; 同时, 若接收到多条CH_ADV信息, 则向所有所属的簇头发送簇成员应答信息CM_RP, 此信息包含该节点的节点号、剩余能量、坐标信息以及所属主簇头节点号.簇头根据接收到的JREQ信息建簇, 再由CM_RP信息建立CH_TABLE. CH_TABLE包含了所有与其有重叠区域簇的簇头节点号, 以及对应重叠区域中的中继节点信息.

2.4 路径建立

在形成簇以后, 需要为每个节点建立数据传输路径.每个感知节点将感知到的信息发送给相应的主簇头节点进行数据融合, 再由簇头开始通过多跳的方式将数据送到基站.

每个簇头根据CH_TABLE中的信息, 首先选出每个重叠区域中剩余能量最高的节点作为候选转发节点; 然后从候选转发节点中选择与基站距离最近的节点作为下一跳数据转发节点.如果某一个簇与任何簇都没有重叠区域, 则簇头在感知范围rs内寻找距离基站最近的簇头节点作为下一跳数据转发节点, 再转发给此簇头的中继节点.之后, 由中继节点选择下一跳数据转发节点.簇头寻找转发节点的流程如图 1所示.

图 1 簇头寻找转发节点算法流程

首先, 中继节点向所有所在的簇对应的簇头节点发送请求信息, 每个簇头选出所有与请求节点不同的重叠区域中距离基站最近的中继节点, 并将此中继节点信息发送给请求的中继节点, 中继节点再从中选择与基站最近的节点作为其下一跳数据转发节点.如果一个簇除发送请求信息中继节点所在的重叠区域外没有其他的重叠区域, 则该簇的簇头节点成为下一跳数据转发节点, 并在其感知范围rs内寻找距离基站最近的簇头节点作为下一跳数据转发节点.通过这样的方式逐步选择下一跳的数据转发节点, 当转发节点与基站距离小于d0时, 直接将数据发送给基站.路径建立算法流程如图 2所示.

图 2 路径建立算法流程
2.5 轮换过程

随着网络的运行, 承担数据转发任务的中继节点和负责簇内数据接收与融合的簇头节点会消耗较多的能量, 为了延长网络生命周期, 均衡网络能耗为中继节点与簇头节点分别设定阈值, 当中继节点和簇头节点的剩余能量低于对应的阈值时, 需要进行节点的轮换.

当中继节点的剩余能量低于阈值时, 簇头会在相同的重叠区域中选择剩余能量最高的节点取代原先的中继节点, 将其作为下一跳数据转发节点.如果一个重叠区域中所有中继节点的剩余能量都小于阈值, 则此重叠区域不再承担数据转发任务.此轮换过程, 整个网络簇结构不会发生改变.

当簇头节点的剩余能量低于阈值时, 网络将重新开始簇头选举、建簇、建立数据传输路由这一过程, 此过程将重新建立网络簇结构.

2.6 OMU算法分簇过程

本节以图 3为例, 说明OMU算法的实现过程.

图 3 网络分簇示例

开始时, 每个节点计算出簇头竞争参数wi, 并得出Twaiti, 如在Twaiti内没有收到其他节点的CH_ADV信息, 则自己宣布成为簇头.簇头再根据式(6)和(7)计算出簇竞争半径并建簇.

处于重叠区域中的中继节点可以同时属于两个及两个以上的簇, 但每个节点的主簇头只有一个.以中继节点R1为例, 同时属于簇头A和B, 它与B的距离小于与A的距离, 因此B为R1的主簇头节点, 接收R1的感知信息.

簇头节点会存储一个CH_TABLE, 包含与其有重叠区域的簇信息及对应中继节点信息.以簇头B为例, 其与簇A、C、D都有重叠区域, 对应的重叠区域中分别是R1R2R3; R3R5R6R7R8; R9.

节点R3, 它会接收到3条CH_ADV信息, 将其存储在CM_TABLE中, 说明此节点为中继节点.

数据传输时, 簇头E将融合后的数据发往重叠区域内的中继节点R10, R10通知簇头D, 簇头D先选出每个重叠区域中能量最高的中继节点作为候选转发节点, 再从候选转发节点中选择与基站距离最近的节点(即R9)作为R10的下一跳数据转发节点, 并按照这样的方法最终将数据传输到基站.

簇头F首先将融合后的数据发送给R11, 但簇G有且仅有这一个重叠区域, 此时簇头F先将数据发送给簇头G, 然后簇头G在rs范围内寻找与基站距离最近的簇头节点(即C)作为R11的下一跳数据转发节点, 之后若一个簇有多个重叠区域, 则按照之前的方法寻找下一跳数据转发节点, 否则按照此方法, 最终将数据发送到基站.

3 仿真分析

本文使用Matlab分别对LEACH、EEOC及本文提出的OMU算法进行仿真.共进行了两组实验, 主要针对网络同一时刻存活节点数量以及节点平均剩余能量进行对比分析.实验参数的选取见表 1, 设置网络共运行1 500轮.

表 1 仿真参数取值
3.1 网络节点分布与分簇结果

图 4给出了在300 m× 300 m的监测区域中随机分布的300个传感器节点位置及首轮分簇的结果, 分簇结果与设计目标一致, 越靠近基站簇半径越大, 节点密度越高簇半径越小.

图 4 首轮网络节点分布
3.2 网络性能分析

下面分析比较两组仿真实验中3种协议的节点平均剩余能量及存活节点数量.节点平均剩余能量表明整个网络的能量消耗情况:平均剩余能量越多, 网络能量消耗越少; 存活节点数量表明网络能耗的均衡状况及覆盖情况:同一时刻存活节点数量越多, 网络能量消耗越均衡, 网络的覆盖程度也越好.

关于实验1网络的仿真结果(图 5)显示, OMU算法在网络节点平均剩余能量方面较LEACH和EEOC有明显的改善.在网络存活节点个数方面, OMU较LEACH有明显改善, 与EEOC相比, OMU虽然更早出现了节点死亡, 但是没有出现EEOC在第1 000轮左右开始的节点大量迅速死亡的情况, 网络运行情况较为稳定.

图 5 实验1仿真结果

图 6是关于实验2的仿真结果, 主要是加大了监测区域的范围.结果表明, OMU较LEACH和EEOC对网络性能有明显改善, 特别是在存活节点个数方面, 无论是出现第1个死亡节点的时间还是存活节点的减少速率方面都表现出了一定优势.

图 6 实验2仿真结果

实验1的仿真结果与实验2的仿真结果相比, 在较大范围内部署传感器节点的情况下, OMU在网络节点平均剩余能量和存活节点个数方面都表现出更大的优势.

4 结论

本文针对静态、非均匀的异构无线传感器网络设计了一种带有重叠区域的多跳非均匀分簇路由算法OMU, 综合考虑节点剩余能量、节点密度及节点与基站距离, 进行簇头选举并建簇, 并在此基础上, 为每个节点建立数据传输路径; 同时, 为簇头节点和转发节点设定能量阈值, 及时进行节点轮换, 避免节点过早死亡.设计了两组仿真实验, 仿真结果表明, OMU算法特别在大规模部署的网络中, 能有效延长网络生命周期, 并能很好地均衡节点功耗, 验证了本文算法的有效性.

参考文献
[1]
Xu Y, Chen L J, Gan L X, et al. Principles and applications of wireless sensor network[M]. Beijing: Tsinghua University Press, 2015: 1-2/9-16.
[2]
Yetgin H, Cheung K T K, El-Hajjar M. A survey of network lifetime maximization tchniques in wireless sensor networks[J]. IEEE Communications Surveys & Tutorials, 2017, 19(2): 828-854.
[3]
Afsar M M, Tayarani-N M H. Clustering in sensor networks: A literature survey[J]. J of Network and Computer Applications, 2014, 46(1): 198-226.
[4]
Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[C]. Proc of the IEEE Hawaii Int Conf on System Science. Hawaii, 2000: 1-10.
[5]
Chen G H, Li C F, Ye M. An unequal cluster-based routing protocol in wireless sensor networks[J]. Wireless Networks, 2009, 15(2): 193-207. DOI:10.1007/s11276-007-0035-8
[6]
Liao Y, Qi H, Li W. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks[J]. IEEE Sensors J, 2013, 13(5): 1498-1506. DOI:10.1109/JSEN.2012.2227704
[7]
Bi X J, Diao P F. Routing and clustering algorithm heterogeneous wireless sensor networks based on gravitational search algorithm[J]. Control and Decision, 2017, 32(3): 563-569.
[8]
Hu Y, Niu Y G, Zou Y Y. A zone-based unequal multi-hop clustering algorithm in WSNs[J]. Control and Decision, 2017, 32(9): 1695-1700.
[9]
Su J S, Guo W Z, Yu Z L. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese J of Computers, 2014, 37(2): 445-456.
[10]
Sun Y J, Lin C L, Jiang H F. An energy efficient distributed uneven clustering routing algorithm for WSNs[J]. Chinese J of Sensors and Actuators, 2015, 28(8): 1194-1200.
[11]
Youssef M A, Youssef A, Younis M F. Overlapping multihop clustering for wireless sensor networks[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(12): 1844-1856. DOI:10.1109/TPDS.2009.32
[12]
Hu Y, Niu Y. An energy-efficient overlapping clustering protocol in WSNs[J]. Wireless Networks, 2016, 24(5): 1-17.
[13]
Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications, 2002, 1(4): 660-670. DOI:10.1109/TWC.2002.804190
[14]
Mhatre V, Rosenberg C. Design guidelines for wireless sensor networks: Communication, clustering and aggregation[J]. Ad Hoc Networks, 2004, 2(1): 45-63. DOI:10.1016/S1570-8705(03)00047-7