MANET网络分簇组网协议比较与分析

刘玉涛，张春晖

(通信网信息传输与分发技术重点实验室，河北 石家庄 050081)

0 引言

移动自组织网，一般称为MANET(Mobile Ad hoc Network)[1]。由文献[2-4]的论述可知，MANET是由一组带有无线收发信装置的移动节点组成的一个无线移动通信网络，它不依赖于预设的基础设施而临时组建，网络中移动的节点利用自身的无线收发设备交换信息，当相互之间不在彼此的通信范围内时，可以借助其他中间节点中继来实现多跳通信。MANET网络与传统的无线通信网络相比，具有以下特点：① 网络的自组织与自恢复特性；② 网络拓扑结构的动态变化[5]；③ 灵活多跳的通信方式；④ 网络的分布式管理与控制；⑤ 短暂的网络生存时间[6]。MANET网络由于上述特点，特别适合应用在战术分队分组通信、反恐处突、抢险救灾和大型集会等临时性或突发性等场合中[7-8]。

在基于簇结构的MANET网络中，分簇组网协议及簇间通信是大规模可靠组网的前提，是一个重要的研究方向。简单高效的分簇算法可以减少MANET网络的路由和计算开销，提高簇间通信效率。现有分簇组网方案的设计一般是基于图论中连通支配集相关理论进行簇头和跨簇节点的选择，文献[9-13]介绍了常用的典型算法包括最大连通度算法、最小ID算法等。本文采用了一种有利于提高跨测通信效率的最大连接度算法，可以有效地保障网络跨簇通信的稳定。在分簇组网进行跨簇处理时，本文设计了一种多信道跨簇处理方式，与单信道跨簇相比，该方式便于实现网络的分层管理与控制，可以实现上层节点同时接入多个下层网络。

1 移动自组织网络系统模型

MANET网络中的移动节点除了需要完成传统无线网络中的业务收发功能外，还具备信息转发功能[14]。MANET网络中节点间是完全对等的，网络的正常工作并不依赖于任何特殊节点，当一个或多个节点离开或加入网络时可以实现网络的动态调整，如图1所示[15]。

图1 MANET网络示意

根据MANET网络的组成特点，可以分为平面化与层级化2种网络结构[16]。基于平面化结构的MANET网络建立、网络管理和结构维护等简单且易于实现；但当网络规模变大时，受制于节点对等性限制，网络计算、管理和维护开销将指数级增长，考虑到节点的移动性引起的控制信息的传输需求，会显著降低网络的有效带宽[17]。

为解决MANET平面化结构引起的网络规模限制问题，参考计算机网络中子网划分的思想，研究人员提出了MANET网络的层级化结构[18]。在这种架构下，可以将MANET网络划分成多个规模可控的子网，子网之间是松耦合关系，能够实现相对独立的管理与控制，在降低网络管理与维护开销的同时有效解决了平面化网络扩展性差的问题，极大地扩展了MANET网络的应用场景。文献[19-22]的研究表明，在MANET网络分层技术中，分簇作为一种简便易行的层级化组网方法，可以有效地提高网络的性能和效率。

2 分簇组网协议

在基于簇的MANET网络层级化结构中，地理上相近的多个节点按照一定的逻辑规则构成不同的簇，并通过网关节点(亦称跨簇节点)连接不同的簇，进而实现全网的连通。一般而言，每一个簇形成一个子网，通常由簇头、普通节点与网关节点组成，其中簇头亦可以用作网关节点，具体与分簇算法有关。

簇头是每个簇的管理者，一般用作网络的管理与调度。簇头可以通过分布式算法由预先设定的标准产生，也可以根据预设的优先级自动产生，自动产生时面临网络融合问题。簇内的普通节点可能同时处于多个簇头的覆盖范围内，但某一时刻最多只能属于一个簇，与一个簇头建立从属关系。网关节点在不同时刻可以隶属于不同的簇，这样一来，即可以实现相邻簇之间的通信，进而达到扩展网络规模的目的。

2.1 簇内组网协议

MANET簇内组网协议主要解决2个方面的问题：① 如何实现节点间同步、网络建立、节点入网和退网；② 如何实现网络资源的管理和控制[21]。基于竞争的组网协议随着网络规模的增加碰撞概率会急剧增高，因此，在规模较大的网络中一般采用基于分配的组网协议[23]。

分布式TDMA协议是一种常用的基于分配的组网协议，将时间划分成互不重叠的帧，然后将帧划分为互不重叠的时隙，将不同时隙与不同的节点ID相对应。每个节点在每个帧周期内均会占有一个TDMA信令时隙，且每个信令时隙均在数据间隔内对应一个可用的数据发送时隙。节点将通过时隙中的信令部分去竞争自己的发送时隙，通过信令时隙申请完成数据的发送。当新节点入网时，其会在本节点选择的时隙发送信令，并在其他时隙进行监听，等待其他节点对自己的确认ACK信息。

Beacon协议是一种基于分配的组网协议，采用信标(Beacon)帧的信道访问机制，主节点周期性地发送信标帧，网络中的其他节点必须遵循主节点分配的时隙进行信道访问。网络中包含3种信标：主信标、代理信标和发现信标。主信标由主节点生成，主信标中包含当前网络的基准时间和时隙分配结果，时隙分配结果决定了网络中节点访问信道的方式和时隙；代理信标由代理站点发送，代理信标中包含主信标的全部时隙分配结构，且携带代理节点的基本属性；发现信标用于发现周围可能的隐藏节点，发现信标中包含用于隐藏节点加入网络的竞争时隙安排，当未入网节点接收到发现信标后，可以根据发现信标中的时隙安排发起加入网络的请求。

建立危险、剧毒、有害、放射性、可传染性物品的全程监控体系，不断列出和修订上述物品清单，通过统一或申报购置，财务报销警示，使用者提供购置、使用、销毁方案等方式对其实行自购置到销毁的一条龙处置方案，经校院两级审批，严格把好使用和监控关。

2.2 簇间通信与分簇算法

分簇和簇间通信需求使得网络中的资源管理或通信过多地集中到簇头和网关节点，不利于事项负载均衡，也不利于平衡节点间的能耗。因此，分簇组网与分簇算法需要重点解决如何减少分簇及跨簇通信中控制信息的开销、如何实现网络拓扑变化时簇内与簇间通信的延续性以及如何实现网络负载的有效均衡等问题。常用的分簇算法有随机算法、最大连接度优先算法、最小标识符优先算法以及链路稳定性优先算法等。

2.2.1 随机算法

随机算法依据发现其他簇中节点的先后顺序选择网关节点，最先接收到其他簇中节点的信息且经过簇头确定后即可以成为该簇的网关节点。网关节点失效后，剩余节点仍旧按照该原则选择新的网关节点。随机算法复杂度低，但不利于降低簇间通信时延，传输效率不高。

2.2.2 最大连接度优先算法

最大连接度优先算法根据节点通过一跳连接的其他簇中节点的个数选择网关节点，顾名思义，跨簇一跳邻居数最多的节点将被定义为网关节点。当多个节点的跨簇一跳邻居数相同时，选择簇内邻居数较少的节点作为网关节点；当簇内邻居数亦相同时，选择ID最小的节点作为网关节点。最大连接度优先算法簇间通信时延较短，但由于连接度随着节点的移动而变化，会导致网关节点的频繁切换。

2.2.3 最小ID优先算法

最小ID优先算法根据能够连接到其他簇的节点的ID选择网关节点，ID最小的被确定为该簇的网关节点。最小ID优先算法收敛较快，但新节点尤其是ID较小节点的加入会导致网关的切换，同时，亦不利于降低簇间通信时延和提高簇间传输效率。

2.2.4 链路稳定性优先算法

(1)

式中，Pr与Pt分别表示接收功率和发射功率；Gr与Gt为收、发两端的天线增益；d表示收发节点间的距离；L为系统损耗率。发端的平均信号强度大的节点被定义为网关节点。链路稳定性优先算法在节点移动的情况下仍旧能最大限度地保障簇间通信的时延，但同样难以避免节点移动引起的网关节点频繁切换。

3 分簇组网中的跨簇处理

分簇组网中簇间通信通过网关节点连接，可以采用单信道方式或双信道方式实现，区别在于簇间连接方式不同。单信道方式网关节点采用单模块，业务跨簇时类似“半双工”，跨簇节点分时工作在2个子网的频率上；双信道方式网关节点采用双模块(可称之为“双卡双待”)，业务跨簇时类似“全双工”，网关节点同时工作在2个子网的频率上。

3.1 单信道跨簇

通过单信道方式连接多个簇时网关节点配置单模块即可，但只能通过时分方式分别接入不同的网络，网络之间是“横连”关系，不存在分层、分级概念，如图2所示。

图2 单信道方式跨簇通信结构示意

3.2 双信道跨簇

通过双信道方式连接多个簇时需要网关节点配置双模块，可以同时接入上、下两层子网，实现网络的分层管理与控制，如图3所示。

图3 双信道方式跨簇通信结构示意

3.3 不同跨簇处理方法的对比与分析

单信道方式网关节点与普通节点采用同样的配置，尺寸和功耗等便于控制。双信道方式便于实现网络分层，组成与实际层级关系一致的网络，按照分层关系组网使用效率更高，如图4所示。双信道方式便于簇间串联，易于扩展网络规模和节点数，且簇间相对独立、互不影响，网络整体更稳定。

图4 双信道方式网络分层管理示意

4 分簇组网簇间通信的实现

下面简要介绍双信道跨簇时簇间通信数据传输的实现途径，考虑准静态应用场景网关节点选择主要依据最大连接度优先算法。

网络应用视图如图5所示，3个不同的簇通过网关节点相连后形成一个分簇多级网。节点连接的业务终端(笔记本电脑等)需要将节点IP设置成默认网关，业务终端的IP地址需要和默认网关保持相同的网段。由图5可知，节点2和节点4为簇间通信的网关节点，当PC1发送数据包到PC2时，PC1默认网关设置为192.168.1.11，PC2默认网关设置为192.168.2.10，具体流程如下：

① PC1发现PC2的IP地址不在同一个簇内，则将数据发送至默认网关，即节点1。链路A中数据包的目的MAC为节点1的MAC，目的IP为PC2的IP。

② 节点1网络层收到数据包，判断IP地址为簇外，查找转发表，找到下一跳IP为192.168.1.14，进而查找IP-MAC表，替换源MAC和目的MAC，将数据发送至该节点，链路B中数据包的目的MAC为节点4的MAC。

③ 节点4收到数据，判断其类型为簇间通信数据包，根据网络号192.168.2.0，将其转发至192.168.2.14。

④ 节点4中IP地址为192.168.2.14的模块判断IP地址为簇内数据包，填写目的MAC为PC2的MAC，源MAC为本地MAC，并将数据包发送至MAC层。然后将数据按照簇内路由发送至节点5。

⑤ 节点5的MAC层直接将数据发送至以太网口。

图5 双信道方式簇间通信实现流程

5 结束语

MANET网络通过分簇和簇间通信可以实现大规模组网。网关节点是实现簇间通信的关键节点，网关节点的选择影响跨簇通信时延、传输效率及簇间通信的稳定性与可靠性。不同的跨簇方式适应不同的应用场景，在准静态效率优先场景下，采用了最大连接度优先算法选择网关节点与双信道跨簇方式。最后，本文以3个自组织网簇为例对分簇组网簇间通信流程进行了详细的分析与介绍。分析可知，本文提出的分簇组网簇间通信采用了最大连接度优先算法和双信道跨簇方法，在充分考虑簇间通信时延的前提下便于工程实现，具有较高的应用价值。

[1] SHARMAA K，TRIVEDI M C.Performance Comparison of AODV，ZRP and AODVDR Routing Protocols in MANET[C]∥2016 Second International Conference on Computational Intelligence & Communication Technology (CICT)，2016：231-236.

[2] 霍金海，王钺，徐赞新，等.基于负载和优先级的MANET优化策略[J].清华大学学报(自然科学版)，2012，52(9)：1270-1274.

[3] ISTIKMAL，KURNIAWAN A，HENDRAWAN.Throughput Performance of Routing Protocols Based on SNR in Wireless Mobile Ad Hoc Networks[C]∥2015 1st International Conference on Wireless and Telematics (ICWT)，2015：1-6.

[4] KUMARJ.802.11 DCF in Dynamic MANET On-demand Routing[J].International Journal of Informatics and Communication Technology (IJ-ICT)，2013，2(2)：85-92．

[5] KIM，DAEHYEOK，SUH，et al.Multi-Rate Combination of Opportunistic Routing and Network Coding：An Optimization Perspective[C]∥IEEE Wireless Communications and Networking Conference：Mobile and Wireless Networks，2012：1947-1952.

[6] 李勇，匡坤高，王平，等.分布式自组织网络动态功率控制机制的研究与实现[J].东南大学学报(自然科学版)，2011，41(2)：296-300.

[7] 卢山，宋志群，贾倩.基于车队行进场景的MANET移动模型研究[J].无线电通信技术，2016，42(1)：9-11.

[8] 陈艺虾，孙权森，徐焕宇，等.SURF算法和RANSAC算法相结合的遥感图像匹配方法[J].计算机科学与探索，2012，6(9)：822-828.

[9] 代家铭，宋玉龙，尚亚黎，等.高动态环境下航空自组网分簇算法设计[J].计算机应用研究，2015，32(4)：1193-1198.

[10] WANG S H，LIU C C，WANG C Y.Link Stability-based Based Routing and Clustering in Ad Hoc Wireless Networks Using Fuzzy Set Theory[J].International Journal of Wireless Information Networks，2002，9(3)：201-212.

[11] 徐丹丹，章勇.一种基于最大连通度的双簇头分簇算法[J].传感技术学报，2008，21(11)：1909-1912.

[12] 杜胜永，柴乔林，王华.基于节点聚合度的生成簇算法[J].计算机应用，2006，26(4)：948-950.

[13] 沙毅，黄烨，黄丽，等.基于小波神经网络预测的Ad Hoc网络分簇算法[J].东北大学学报(自然科学版)，2011，32(9)：1233-1236.

[14] 李秀朋，李少辉.一种Ad Hoc自组织网络系统的设计与实现[J].无线电工程，2014，44(8)：8-10.

[15] 齐法制，张红梅，张瀚文，等.MANET网络中基于队列长度的逐跳AC自适应调整机制[J].计算机科学，2016，43(3)：84-88.

[16] 刘春旭，刘元安，高锦春，等.大规模MANET中基于分层架构的分簇式发布-订阅路由协议[J].吉林大学学报(工学版)，2013，43(2)：451-458.

[17] YONEKIE， BACONJ.An Adaptive Approach to Content-based Subscription in Mobile Ad Hoc Networks[C]∥Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops，2004：92-97.

[18] BAKERD，EPHREMIDES A.The Architectural Organization of a Mobile Radio Network via A Distributed Algorithm[J].IEEE Transactions on Communications,1981，29(11)：1694-1701.

[19] 何鹏，阎保平，李志，等.CM-MAC：一种基于分簇的多信道车载网MAC协议[J].计算机研究与发展，2014，51(3)：502-510.

[20] 高键鑫，吴晓平，吴旭升.采用信任度量的MANET网络分簇模型[J].北京邮电大学学报，2014，37(S1)：125-130.

[21] 冯文江，吴迪.链路可用性的MANET网络分簇算法[J].重庆大学学报，2010，33(12)：109-113.

[22] 秦茜，宋志群，刘玉涛.一种固定分配与动态竞争结合的MAC层协议算法[J].无线电工程，2017，47(2)：11-14.

[23] MILES J，MUKNAHALLIPATNA S，KUBICHEK R F，et al.Use of Radio Propagation Maps in a Single Moving Beacon Assisted Localization in MANETs[C]∥2014 International Conference on Computing，Networking and Communications (ICNC),2014：871-877.