基于MAP-ICC的无线Mesh网络层次路由协议研究*

龙昭华，蒋纬昌，刘达明

（重庆邮电大学计算机科学与技术学院，重庆400065）

基于MAP-ICC的无线Mesh网络层次路由协议研究*

龙昭华*，蒋纬昌，刘达明

（重庆邮电大学计算机科学与技术学院，重庆400065）

在研究混合路由协议HWMP和低功率自适应层次路由算法LEACH基础上，提出一种基于能量均衡的层次路由算法MAP-ICC（Mesh Access Point Independent Construction of Cluster）。该算法针对无线Mesh网络中的接入层MAP节点进行独立建簇，以MAP节点的能量消耗为依据计算最佳簇首个数，根据最佳簇首个数对覆盖的环形区域内的MAP节点进行分簇，用户节点根据加权公式选择合适的簇首加入。仿真实验结果表明：提出的MAP-ICC独立建簇算法一定程度上增加了网络生存时间，提高了数据报文发送成功率和降低了路由负载。

无线Mesh网络；建簇机制；能量消耗；层次路由协议；最佳簇首

EEACC：6150P doi：10.3969/j.issn.1004-1699.2016.10.018

IEEE802.11s［1］中定义的无线Mesh网络架构具有三层结构如图1所示：MPP节点具有网关功能并且与有线网络相连，作为Mesh Tree的根父亲节点可以对整个无线Mesh网络进行管理。MP节点支持自动拓扑设置、路由自动发现、数据包转发、形成Mesh网络多跳骨干网。MAP节点提供Mesh接入，具有转发功能和较小移动性。STA（Station）只具有接入功能的节点并且具有移动性。无线Mesh网络是在Ad Hoc网络［2］和WLAN网络的基础上发展而来，现有对无线Mesh网络的研究大都集中在路由协议分析和接入认证［3］上，对接入端MAP节点的研究较少。对于在无线Mesh网络中使用分簇方法去优化网络结构的研究也相对较少。

图1　IEEE802.11s无线Mesh网络结构图

IEEE802.11s中默认的无线 Mesh路由协议HWMP［4］（Hybrid Wireless Mesh Protocol）提供两种不同的模式：①按需路由模式，②先验式路由模式。在传输骨干网上采用先验式路由模式和在接入端采用按需路由模式。多数层次路由协议如：LEACH［5-6］协议、HEED［7］协议、EECS［8］协议和TEEN［9］协议等都是采用建簇的方式来调整网络结构，但是在无线Mesh网络中骨干节点几乎不移动且主要是转发通信，只有STA、MAP节点会发生移动，传统的分簇机制［10］不适合在无线Mesh网络中使用，必须设计针对无线Mesh网络的路由协议［11］，因此本提出MAP-ICC独立建簇算法。

本文主要贡献：①区分无线Mesh网络节点类型对MAP节点独立建簇，计算最佳簇首个数，STA与簇首进行连接，有效避免节点间干扰，STA在数据传输时不会出现环路、绕路、提高节点间数据传输效率。②针对不同类型节点具有不同功能的特点，结合无线网络结构中分簇的思想和无线Mesh网络中先验式树状结构模式，在骨干节点间使用先验式路由模式，在MAP、STA节点间采用按需路由模式，这避免了同一节点在两种模式下切换带来切换时延［12］。对簇域内的节点满足条件情况下随机选择簇首，避免轮询选簇首时带来的时延。

1　基于分簇机制的层次路由协议

无线Mesh网络中的路由协议分为多种，根据网络逻辑结构分为平面路由协议和层次路由协议。在层次路由协议中，网络中节点通常被划分为簇（Cluster），每一个簇有一个簇首（Cluster Head）节点和多个叶子节点（Leaf Node）组成。多个簇首节点组成高一级网络，高一级网络再次分簇，再次形成高一级网络直至最高级。在分层结构中，簇首节点不仅负责收集簇内信息，同时进行信息处理和簇间转发数据，可减少同基站间的回传次数。IEEE802.15.5［13-14］和 ZigBee［15］是采用树形结构来构建网络，并结合区分服务 Diff-Serv［16］的思想即不改变网络基础结构增加区分服务的功能。这对无线Mesh网络的构建有很大的启发。

文献［6］提出LEACH协议，即低功率自适应层次路由算法。该算法引入簇的概念，通过等概率地随机循环选择簇首，簇首向周围节点广播消息，每个节点根据接收到广播信号的强弱来选择加入哪个簇。簇内节点把数据发送给簇首，簇首将数据融合后发给基站。一段时间后，重新进行建簇。

LEACH协议的簇首选择过程如下：每个节点产生一个［0，1］的随机数，如果随机数小于阈值T（n），则选取该节点为簇首。当选取簇首后，把阈值T（n）设置为0，可以避免再次当选簇首。T（n）的计算公式如式（1）：

其中k为簇首节点占网络中的全部节点的百分比，r为已经完成的回合数（即轮数），为每轮被选出的簇首节点的数目，G为还没有被选举为簇首的节点集合。但是LEACH协议存在如下不足之处：没有考虑到簇首节点的覆盖范围，可能会出现一些边缘节点。k的值与网络规模和节点密度有关，k的最佳值无法确定。可能存在簇域间有无法覆盖的区域，其中虚线圆形为簇域，如图2所示。

图2　簇域形状示意图

文献［7］中提出HEED协议是一种混合式的分簇协议。在选簇首时根据节点剩余能量来概率性的选取候簇首节点，最后再以簇内节点通信代价的高低来选取簇首。但该协议在考虑节点移动性方面不足。

文献［8］中提出的EECS协议，该协议主要是在组簇阶段以概率T产生候选簇首节点，并且选取一个固定半径范围内的节点根据其剩余能量的大小进行选簇首。但是该协议存在簇头分布漏洞、节点在加入簇首时未考虑节点剩余能量等问题。

文献［9］中的TEEN协议是基于LEACH协议进行改进的，通过增加硬阈值 HT（Hard Threshold）和软阈值ST（Soft Threshold）来控制节点发送数据时机。该方法有效减少数据传输次数，但是当满足阈值的时候进行数据传输，容易造成信号干扰，若采用TDMA方法，则会引起数据延迟，并且该方法用在无线Mesh网络中过于复杂。

设计简单高效、能量均衡，传输效率高的分簇算法来支持无线Mesh网络是十分必要。基于此，本文提出MAP-ICC独立建簇算法，该建簇路由机制有以下几个优点：①簇首节点把本簇内的数据融合处理后再进行转发，减少STA节点与根父亲节点的通信数据量，节省了传输能耗。②采用分簇路由机制便于结构管理，有利于分布式算法的使用，扩展性较好，适合具有大规模的STA。③无线Mesh网络中根据节点类型设置不同的策略，简化了无线Mesh网络中节点功能，提高效率。④簇内节点采用单跳按需路由通信，简单易实现。MAP节点到MPP节点采用多跳先验式路由通信，保证较小的时延。⑤根据最优簇首个数，STA节点根据加权值选择与周围的簇首相连，有效减少节点间的干扰，提高网络吞吐量。

2　MAP-ICC独立建簇算法

MAP-ICC独立建簇算法分为三个阶段：①选举簇首MAP节点，②簇首节点广播消息，STA节点选择合适的簇首加入，③数据传输。

2.1MAP-ICC独立建簇算法的设计

MAP-ICC独立建簇算法模型：

在无线Mesh网络中N个MAP节点随机部署在一定范围的区域内，用 pn表示无线Mesh网络中第n个MAP节点。在无线Mesh网络中节点的集合为pn=｛p1，p2，p3，…，pn｝，并且作如下假设：①每个MAP节点具有全网唯一ID，随机分布在MP节点周围；②与MAP节点相连的MP节点充当基站，以基站MP为坐标原点（0，0）并且MP节点位置固定不变，在无线Mesh网络组建时，每个MAP节点完全一样；③MAP节点可以获知自己的能量剩余和通过GPS获知位置信息；④MP节点通过固定电源供电，不考虑其能耗问题，具有多跳、数据转发、数据处理、自组织等能力，多跳之间采用先验式路由协议；⑤通信端STA节点都在MAP节点的通信范围之内，MAP节点在MP节点的通信范围之内；⑥并假设不参与通信的MAP节点的能量消耗忽略不计。

2.2组簇机制

MAP-ICC独立建簇算法的产生过程分为如下7步，结合图3和图4对MAP-ICC独立建簇算法在无线Mesh网络中建簇过程进行简单说明。

图3　MAP-ICC独立建簇算法网络结构示意图

图4　MAP-ICC独立建簇算法簇域形状示意图

（1）网络初始化：通过GPS获得每个MAP节点的位置信息，然后将MAP节点的位置信息和能量信息广播给基站MP，由基站MP进行统计和计算。

（2）MP的通信半径为R，在［R/2，R］的范围的bced扇形区域中进行簇首选择，其中∠cae=β为扇形区域对应的角度。其大小根据区域内MAP节点数量进行动态调整。其中R的计算式（2）表示：

其中L是与传输无关的系统损耗，hs是发射节点的天线高度，hr是接收节点的天线高度，λ是载波信号的波长。

（3）对扇形区域内的MAP节点以等概率随机选择MAP作为簇首，选择成为簇首的节点向周围节点广播信息，宣布自己成为簇首，并把自己标记位r置为1（1表示簇首，0表示成员节点），非簇首节点进入深度睡眠状态。

（4）计算最佳簇首个数。STA节点要通信时，采用单跳方式通过簇首MAP节点向MP节点通信。根据最佳簇首个数多少，动态调整簇域的大小和簇首节点个数。最佳簇首个数的主要以能量消耗为依据，其方法如下：

①采用文献［17］中的能量消耗模型，传输距离d小于R时采用自由空间传输模型，传输距离d大于R时采用多路衰减模型。本文中簇域均在MP通信半径范围内，因此采用自由空间传输模型。节点发送或接收mbit数据所消耗的能量如式（3）：

其中，E1是节点接收或发送单位数据所消耗的能量，单位是J/bit，μfs是自由空间传输系数，单位是J/（bit·m2），μma是多路衰减传输系数、单位是J/（bit·m4）。

②每个簇首节点的能量消耗主要有：接收来自非簇首节点数据包、数据融合、数据包转发，其它能量消耗忽略。为方便计算，假设有N个节点分布在a×a的正方形区域内。若基站MP周围分k个簇，则各个簇内节点数是N/k，则每个簇内有（N/k-1）个非簇首节点。因此在发送m bit数据时能量消耗Econsume的表达式如式（4）：

其中，E2表示数据融合能量消耗，d1是簇首MAP节点到基站MP节点之间的距离，其大小由GPS获得的位置信息来计算。d2表示簇域内的非簇首节点到本簇内簇首节点的距离。假设在簇域内MAP节点分布概率为ρ（x，y），MAP节点均匀分布在整个网络中，每个簇所覆盖的面积为可求簇半径R如式（5）：

非簇首节点到簇首节点距离平方的数学期望为式（6）所示，并把式（5）带入式（7）可化简为式（8）

由于假设节点在区域内是均匀分布，则分布概率ρ=（1/（a2/k），带入式（7）可化简为式（8）：

将式（8）带入到式（4）中得整个网络总能量消耗如式（9）：

可知总能量消耗Esum是关于簇域个数的函数，对簇域个数k求导，在导数为零的情况下Esum能够取得最小值，得到最小值的k，则可求最优簇首个数为式（10），计算最佳簇首个数：

③根据最佳簇首个数kopt与总的MAP节点个数的比例关系，计算在图3中环形区域内簇首个数和簇的个数。

（5）周围的STA节点就近选择簇加入，优先选择与簇首建立连接。在选择加入哪个簇时，根据加权公式判断STA节点加入哪个簇首，加权式（11）、式（12）、式（13）：

其中，R1表示STA节点到簇首MAP节点的距离，d2表示簇首MAP节点到基站的距离，dR1_max表示节点到簇首最大距离的期望，d2_min簇首MAP节点到基站最小距离，d2_max簇首MAP节点到基站最大距离，f子函数用来保证距离STA节点最近的簇首，g子函数用来使节点加入距基站更近的簇首。

（6）在网络传输过程中，当簇首的能量下降到预先设定阈值时，放弃该节点为簇首，并把该节点进行标记，写入一个非簇首表中，表示该节点之后不会再被选为簇首。

（7）进入下一轮选簇首阶段，重复步骤（3）～步骤（6）操作，直至所有的MAP节点都被选过簇首且其能量剩余小于设定阈值。

2.3数据结构和报文设计

针对MAP-ICC独立建簇算法，定义了节点数据结构和报文结构：

①节点的数据结构

②节点的报文设计：

MAP-ICC独立建簇算法中使用的报文格式见表1，消息类型见表2。

表1　MAP-ICC独立建簇算法报文格式

3　仿真分析

3.1仿真环境与参数设置

实验用MATLAB作为仿真工具，对本文提出的MAP-ICC独立建簇算法进行仿真分析，分别从网络生存时间、数据报发送成功率、路由负载进行分析对比。实验环境为以基站MP为圆心圆形覆盖区域内，区域内MAP节点均匀分布，STA节点随机分布。网络半径R为200 m、MAP节点个数300、节点初始能量0.5 J、数据包大小2 000 bit、电路固定能耗E1为50、自由空间传输系数为10、多路衰减传输系数为0.001 3。

3.2仿真结果分析

3.2.1网络生存时间

网络生存时间用来反映在网络运行过程中节点能够维持网络通信的最长时间。随着网络运行时间的推移，一些节点因能量耗尽而死亡，根据最后一个存活节点的死亡时间来判断网络生存时间。从实验结果图5可知本文提出的MAP-ICC独立建簇算法最后一个节点死亡时间要相对较晚，这是因为非簇首节点进入深度睡眠状态而减少能量的消耗，从而延长了网络的生存时间。

3.2.2数据报文发送成功率

数据报文发送成功率是目的节点成功接收到的数据报文数量与发送节点发送的总报文数量的的比值，是用来反映链路的稳定性和路由协议的优劣。从实验结果图6来看，本文提出的MAP-ICC独立建簇算法在开始时数据报文发送成功率略低，这是因为在起始阶段要进行建簇而需要发送多余的报文，从而导致其报文成功率略低。但是在大部分时间内MAP-ICC独立建簇算法的报文发送成功率要高于HWMP和LEACH。

3.2.3路由负载

路由负载用来反映在传输链路上发送一定量报文时节点或链路所负载的报文量或报文的比例。同样条件下路由负载越小表示链路负载越小或者节点业务承载量越小。从实验结果图7可知MAP-ICC独立建簇算法在整个网络运行过程中当节点数量约小于250个节点时路由负载相对较小。

图5　网络生存时间对比

图6　数据报文发送成功率

图7　路由负载与节点个数的比较

4　结束语

该文分析了传统的分簇路由协议，并且针对无线Mesh网络中节点类型不同功能不同的特点提出MAP-ICC独立建簇算法，通过对MAP节点进行独立建簇，在网络生存时间、数据报文发送成功率、路由负载三个方面进行仿真分析对比。实验得出本文提出的MAP-ICC独立建簇算法具有良好的表现结果。

［1］胡志强.基于802.11s的无线Mesh网络架构设计与路由机制研究［D］.北京：北京邮电大学，2014：9-27.

［2］杨双懋，郭伟，唐伟.一种最大化网络吞吐量的认知无线Ad Hoc网络跨层优化算法［J］.计算机学报，2012（3）：491-503.

［3］肖跃雷，王育民.可信环境下的WLAN接入认证方案［J］.兰州大学学报，2013（4）：547-553.

［4］林晖，马建峰.无线Mesh网络中基于跨层信誉机制的安全路由协议［J］.西安电子科技大学学报，2014（1）：116-123.

［5］叶继华，王文，江爱文.一种基于LEACH的异构WSN能量均衡成簇协议［J］.传感技术学报，2015，28（12）：1853-1860.

［6］孙彦景，林昌林，江海峰.一种能量高效的分布式非均匀分簇路由算法［J］.传感技术学报，2015，28（8）：1194-1200.

［7］杨梦宁，杨丹，黄超.无线传感器网络中改进的HEED分簇算法［J］.重庆大学学报，2012（8）：101-106.

［8］尚凤军，Mehran Abolhasan，Tadeusz Wysocki.无线传感器网络的分布式能量有效非均匀成簇算法［J］.通信学报，2009（10）：34-43.

［9］陈东海，李长庚.基于簇头功能分化的无线传感器网络成簇算法［J］.传感技术学报，2015，28（2）：244-248.

［10］龙胜春，卢定乾，池凯凯.基于同构传感器网络的能量空洞避免策略［J］.传感技术学报，2016，29（1）：103-108.

［11］乔宏，张大方，谢鲲，等.分布式多网关无线mesh网公平协作路由算法［J］.通信学报，2015（2）：179-189.

［12］陈康先，陆以勤，罗旭光，等.无线网状网域间无缝切换技术研究与设计［J］.华南师范大学学报，2015，47（4）：150-154.

［13］史晓晨，刘凯明，高锦春，等.无线个域网mesh网络标准——IEEE802.15.5［J］.计算机应用研究，2011，28（1）：243-246.

［14］钱亮，钱志鸿，李天平，等.基于强化学习的IEEE802.15.4网络区分服务策略［J］.通信学报，2015（8）：171-181.

［15］钱志鸿，朱爽，王雪.基于分簇机制的ZigBee混合路由能量优化算法［J］.计算机学报，2013，36（3）：485-493.

［16］林闯，单志光，盛立杰，等.Internet区分服务及其几个热点问题的研究［J］.计算机学报，2000，23（4）：419-433.

［17］Heinzelman W R，Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1（4）：660-670.

龙昭华（1962-），男，贵州遵义人，硕士生导师，教授，CCF会员，计算机学会传感器网络专委会委员、计算机学会普适计算专委会委员，主要研究方向：为网络通信、嵌入式系统，longzha@cqupt.edu.cn；

蒋纬昌（1989-），男，河南南阳人，硕士研究生，CCF学生会员；会员号：58706G，主要研究方向：无线传感器网络、无线Mesh网络，jiangwc_ny@163.com。

The Research of Wireless Mesh Network Hierarchical Routing Protocol Based on MAP-ICC*

LONG Zhaohua*，JIANG Weichang，LIU Daming
（College of Computer Science and Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，Chana）

In the research of Hybrid Wireless Mesh Protocol and Low Energy Adaptive Clustering Hierarchy，propose a hierarchical routing algorithm MAP-ICC（Mesh Access Point Independent Construction of Cluster）based on energy balance.The algorithm for Wireless Mesh Network access layer MAP node independent clustered，the energy consumption of node MAP calculate the optimum number of cluster head，based on the optimal number of cluster head node for MAP within the coverage area is divided cluster，users select the appropriate cluster head node to join with the weighted formula.The simulation results show that：the propose MAP-ICC independent clustered algorithm has increased survival time，improve the success rate of data packets and routing load reduced.

wireless mesh network；build cluster mechanism；energy consumption；hierarchical routing protocol；optimal cluster head

TP393

A

1004-1699（2016）10-1573-06

项目来源：重庆市研究生教学改革研究项目（yjg143097）

2016-04-27修改日期：2016-05-30