一种基于多信道分簇结构Ad Hoc网络的簇间中继实现方案

王 迪（南京邮电大学通信与信息工程学院，江苏南京210003）

一种基于多信道分簇结构Ad Hoc网络的簇间中继实现方案

王 迪
（南京邮电大学通信与信息工程学院，江苏南京210003）

针对大规模应急救援场景，将多信道接入信道利用率高、网络吞吐量大的优点与分簇式Ad Hoc网络减少开销、便于管理的特征相结合，设计出基于分簇结构的Ad Hoc网络模型，提出了与之相对应的支持多业务的多信道混合接入协议。在此协议基础上，对节点间通信方案进行了探讨，并详细阐述了簇间中继通信的实现方案及流程。

Ad Hoc网络；多信道接入；分簇结构；簇间中继

O 引言

与传统网络相比，Ad Hoc网络无需依赖于任何预先布置的固定基础设施，具有网络方便快捷、灵活性高、抗毁性强等优点，在军事战场、紧急救灾、公共服务等场合发挥了重要作用，也成为近年来人们研究的热点。Ad Hoc网络结构可以分为平面式和分簇式两种［1-2］，平面结构可扩充性差，适合于小规模网络，而在大规模应急救援时网内节点数量较多且不断变化，采用分簇结构将更加适合。

在Ad Hoc网络中，节点能量有限，发射功率较小，辐射范围有限，往往需要多跳才能达到目的节点，如果使用单信道通信，可能导致隐藏/暴露终端的问题［3］，影响MAC协议的性能。为了解决该问题，人们提出了多信道MAC协议，它不仅可以解决隐藏/暴露终端问题，还能提高网络吞吐量，容纳更多的用户，更适合于分簇结构的Ad Hoc网络。因此，本文将基于多信道分簇结构Ad Hoc网络的框架进行讨论。

1 相关工作

目前，关于分簇结构Ad Hoc网络的节点通信方案的理论研究［4-7］有很多，其中簇间通信的职责由簇头承担，而簇头本身还需要对簇内普通节点进行维护管理，当簇头节点出现故障时，该簇将与其他簇失去连接，成为网络性能提升的瓶颈。参考文献［8-10］中对于该问题提出了不同的改进方法，但都是基于优化簇头选举和分簇算法的，并没有真正解决簇头负担过重的问题。参考文献［11］提出了用网关节点来转发簇间通信，但是当两个归属于不同簇的节点可以直达时，如果仍然交给固定的网关节点转发，则无法实现最优路径，造成一定的资源浪费。

另一方面，在分簇结构Ad Hoc网络的基础上，结合多信道MAC协议的研究目前还比较少。参考文献［12］虽然为簇内和簇间通信提供了基于分簇结构的多信道调度算法，但是其只适合基于时隙分配的通信，不适合突发业务。参考文献［13］也提出了一种基于分簇结构的多信道管理协议，并为不同的业务需求提供了竞争和非竞争两种类型，但仍然存在频谱资源管理复杂、簇间通信依靠指定节点存在瓶颈等问题。参考文献［14-16］都是基于车载无线自组织网，这是一种特殊的移动性自组织网，其中节点高速移动、电量充足，不适合应急救援场景。

本文基于多信道分簇Ad Hoc网络的结构基础，针对节点间通信，特别是簇间通信提出一套实现方案。首先定义了系统的模型框架和运行机制，并提出了基于分簇结构的多信道混合接入协议，用于满足不同服务质量（Qua1ity of Service，QoS）需求的业务，最后针对簇间中继提出了具体的实现方案。

2 系统模型

在应急救援场景下，Ad Hoc自组织网络需要支持多业务通信，如信令、短数据包等对实时性要求不高的业务，以及语言、视频等对时延和带宽都有一定要求的实时业务，因此本文采用了多用户混合信道接入机制，在IEEE 802.11e MAC协议［17］的基础上提出以下更适合多信道分簇结构Ad Hoc网络的系统模型。

系统宽带被分为1个公共控制信道（Common Contro1 Channe1，CCC）和n -1个数据信道（De1icated Channe1，DCH）。网络中全局共享CCC信道，每个簇都有属于自己的数据信道DCHi，簇内节点都在该频点收发数据。为了实现多信道通信方案，节点必须至少配备两个接收机分别监听CCC信道和DCHi信道，综合考虑通信效率和设备成本，本文采用由一个半双工发送机和两个半双工接收机构成的硬件设备来完成通信任务。

在分簇结构的Ad Hoc网络中，节点分为主控节点、簇头节点、普通节点和中继节点4种类型。其中主控节点通过管理簇头节点来管理整个网络，簇头节点管理本簇内的普通节点，中继节点用于不能直连的节点间的通信。网络结构如图1所示。簇B中簇头用B表示，簇内普通节点用b1、b2表示，簇内数据信道用DCHB表示，以此类推。

图1 分簇结构Ad Hoc网络模型

3 基于分簇结构的多信道混合接入协议

信道周期性地划分为帧来进行多用户、多业务的接入管理。每个超帧由N个长度相等的复帧构成。在每个复帧头部，主控/簇头节点在CCC/DCHi信道广播BEACON帧，用于节点同步、告知CFP时隙分配表等。每个节点会周期性地在CCC信道上发送身份广播帧（HELLO帧），用于向周围节点告知自己的节点信息以及两跳范围内的邻居节点表。每个复帧可分为竞争时段（Contend Period，CP）和非竞争时段（Contend -Free Period，CFP），分别对应时隙竞争接入和时隙分配接入。在CP时段，节点间采用CSMA/CA机制避免碰撞，适合传输控制帧、短数据包等突发业务；在CFP时段，节点采用TDMA接入方式，把信道划分为若干个时隙，每个时隙内只允许一个节点发送数据帧，每个节点根据自身业务需求在CP时段发送时隙申请帧，并等待主控/簇头在BEACON帧中广播时隙分配表，适合实时的长数据包传输。

本系统模型的优点在于可根据业务需求灵活变化。因为每一复帧内CFP时段开始时间由主控/簇头控制并在BEACON帧中广播，当网内节点数较多，需要传输的数据业务量大时，可以适当缩短CP时段长度，在CFP时段多安排几对通信节点；当网络拓扑变化大，需要大量的控制帧管理更新时，可以适当延长CP时段长度，减少数据传输。此外，当主控/簇头在分配时隙时，会根据业务类型的重要性、节点权值等信息进行判断，并且在将时隙分配出去后，仍对信道保持监听，如果连续若干个复帧内，某个被分配的时隙段都没有数据传输，主控/簇头将收回该时隙段重做安排。通过上述方式，可大大提高信道利用率，保证通信质量。

4 簇间中继实现方案

对于分簇结构的Ad Hoc网络，节点之间的通信可以分为簇内通信和簇间通信。对于簇内通信，节点可以通过HELLO帧获得本地路由表直接通信。

在本方案中，簇间通信不再依赖于某一节点，而是根据自身的路由信息找到最佳路径。由于每个簇的数据信道频点不同，节点之间无法直接通信，需要切换信道或者借助中继节点才能实现连接。对于非实时业务，只需在发送时切换频点便可实现簇间通信，而实时业务的通信比较复杂，具体分为以下3种情况：（1）节点之间为邻居节点，可以直达；（2）节点之间为两跳路由，需要一个同簇中继节点转发；（3）节点之间为两跳路由，中继节点与收发双方均不同簇。至于更复杂的情况，会导致时延过长，且跨越多个簇，网络情况难以预测，可以参考文献［8-10］，借助簇头甚至主控节点发射功率大、辐射范围广的特点减小簇间跳数实现通信，本文不再赘述。

4.1 簇间一跳节点通信方案

当簇间一跳节点如图1中a1、b1所示，通信双方在彼此的功率辐射范围内，节点能在CCC信道上收到对方广播的HELLO帧，并知道对方所在的簇号以及数据信道的频点，此时与簇内通信情况大致相同，具体通信流程如图2所示。

节点a1先在CCC信道CP时段向b1发送簇间时隙申请帧，该帧中包括了目的节点ID号、要发送的数据帧长度等信息，由于所有节点都在CCC信道上监听，可以有效避免碰撞。b1收到后得知不同簇的节点a1要向自己发送实时业务，即替a1向簇头B申请DCHB信道CFP时隙段。簇头B收到簇间时隙申请之后，不同于一般的簇内时隙申请帧会得到一对时隙，簇间一跳通信只需要一个时隙，并在下一复帧开始通过BEACON帧广播。节点b1收到DCH_BEACON帧后记录下a1被分配的时隙段，并通过簇间时隙回应帧告知a1。与此同时，为了减小簇间通信时延，a1在向b1发送簇间时隙申请帧之后，将发送信道立即切换到DCHA上，替b1向本簇簇头A申请DCHA信道一个CFP时隙。

图2 簇间一跳节点通信流程图

4.2 簇间两跳节点通信方案

当收发双方在两跳范围内，通过自己周围邻居节点广播的HELLO帧中一跳节点表能找到对方，即在本地的二级邻居节点表中找到目的节点，则将该一级邻居节点作为中继节点；如果存在多个一级邻居节点能到达的节点，那么将根据信道状态、剩余电量、移动性等评估节点权值，综合选出最适合的节点作为中继节点。此时又分为两种情况：

（1）中继节点与其中一个节点同簇

如图1所示，当b2想与c4通信并选择c3作为中继节点时，通信流程如图3所示。

图3 簇间两跳节点通信流程图（中继节点与其中一者同簇）

首先，b2在本地路由表中找到最适合中继的节点c3后，会先替候选c3向本簇簇头B申请1个簇间时隙，收到B分配的时隙后，b2以高优先级发送中继请求帧，告知c3为候选节点，中继转发与c4的通信，并附带已申请的簇内CFP时隙和要发送的数据长度；c3随后向c4发送簇间时隙申请帧，并告知源节点是b2，自己是中继一跳节点；c4收到后向簇头C发送簇间申请帧，替自己和b2、c3一共申请3个时隙，簇头C广播回应后，簇内节点c3、c4会解析出被分配的时隙段，c3也会记录下b2被分配的时隙段，通过中继确认帧告知，并将自己的节点属性改为中继节点（发送优先级更高）。当b2收到c3的中继回应帧表明簇间中继请求成功，b2、c3、c4只需要在被分配的时隙选择对方的信道发送数据帧即可。

（2）中继节点与两个节点均不同簇

如图1中，c1要与d1建立通信，与（1）大致相同，只不过中继节点e1需要替c1、d1向簇头E申请两个时隙，通信节点c1和d1要分别替e1申请一个时隙。限于篇幅不再详述。

值得一提的是，本文提出的基于分簇结构的多信道混合接入协议，会对分配后的时隙实时监控，监听已分配的时隙段是否有数据传输，如果连续多个复帧都没有使用则将时隙收回。而上述方案中，簇头C在为e1分配时隙后，由于链路存在多跳时延，可能存在连续多个复帧内都没有数据传输，因此簇头C可推迟几个复帧再进行分配，避免资源浪费。

5 结论

本文根据现有的应急救援需求，充分利用分簇结构Ad Hoc网络分簇管理的特征，结合多信道接入方案信道利用率高、网络吞吐量大的优点，在现有的IEEE 802.11e接入方案的基础上，提出了基于分簇结构的多信道混合接入协议，满足了不同业务的QoS需求。网络中的硬件设备由一个半双工发送机和两个半双工接收机构成，既满足了多信道接入的需求，又不需要频繁地切换信道，是成本与性能折中后的最佳方案。在此基础上，对节点通信方案进行了研究，并针对相对复杂但现有研究比较少的簇间中继通信的情况，给出了详细的实现方案。该方案结合分簇、多信道的优点，管理灵活，简单易实现，对于实践具有较好的参考作用。未来工作将进一步完善多信道分簇结构Ad Hoc网络的接入协议和实现方案，结合应急通信的特殊环境，进一步优化方案，将本方案在硬件平台上进行实现并验证。

［1］王海涛.Ad Hoc网络体系结构及其设计［J］.中国数据通信，2003，5（8）：70-77.

［2］马东冉，张科.Ad Hoc网络的体系结构分析［J］.重庆科技学院学报（自然科学版），2007，9（3）：63-65.

［3］兰丽，单志龙.Ad Hoc网络中隐藏终端和暴露终端相关问题研究［J］.计算机与数字工程，2010，38（7）：36-40.

［4］RAJAMANICKAM V，VEERAPPAN D.Inter c1uster communication and rekeying technique for mu1ticast security in mobi1e ad hoc networks［J］.Iet Information Security，2014，8（4）：234-239.

［5］ADUWO A，ANNAMALAIA.Channe1-aware inter-c1uster routing Protoco1 for wire1ess ad-hoc networks exP1oiting network diversity［C］.IEEE Vehicu1ar Techno1ogy Conference，2004：2858-2862.

［6］Hong Xiaoyan，Xu Kaixin，GERIA M.Sca1ab1e routing Protoco1s formobi1e Ad Hoc networks［J］.IEEE Network，2002，16 （4）：11-21.

［7］CHIANG C C，WU H K，LIU W，et a1.Routing in c1ustered mu1tihoP，mobi1e wire1ess networkswith fading channe1［C］.In Proceedings of IEEE SingaPore Internationa1Conference on Networks（SICON），1997：197-211.

［8］CHATTERJEE M，DAS S K，TURGUT D.WCA：a weighted c1ustering a1gorithm formobi1e Ad Hoc networks［J］.Journa1of C1uster ComPuting，2002，5（2）：193-204.

［9］SAFWAT A，HASSANEIN H S，MOUFTAH H.Power-aware fair infrastructure formation for wire1essmobi1e Ad Hoc communications［C］.IEEE G1oba1Te1ecommunications Conf.，2001：2832-2836.

［10］AL-KAHTANIM S，MOUFTAH H T.A Stab1e c1ustering formation infrastructure Protoco1in mobi1e Ad Hoc networks［C］. IEEE Int.Conf.on Wire1ess Communications Networking and Mobi1e ComPuting，2005：406-413.

［11］TSENG C C，CHEN K C.QoS-guaranteed Po11ing-based 2-1ayer integrated mu1tihoP schedu1ing a1gorithm for wire1ess ad hoc networks［C］.Vehicu1ar Techno1ogy Conference，2004 IEEE 59th，2004：2144-2148.

［12］LEE H，LIM C C，CHOI J.C1uster-based mu1ti-channe1 schedu1ing a1gorithms for ad hoc networks［C］.W ire1ess and OPtica1 Communications Networks，2007.IFIP Internationa1 Conference on.IEEE，2007：1-5.

［13］YU G J，CHANG C Y.An efficient c1uster-based mu1ti-channe1management Protoco1 for wire1ess Ad Hoc networks［J］. ComPuter Communications，2007，30（8）：1742-1753.

［14］ZHANG X，SU H，CHEN H H.C1uster-based mu1ti-channe1 communications Protoco1s in vehic1e ad hoc networks［J］. IEEE W ire1ess Communications，2006，13（5）：44-51.

［15］WANG K L，WANG T P，TSENG C C.A fair scheme for mu1ti-channe1 se1ection in vehicu1ar wire1ess networks［J］. Wire1ess Persona1Communications，2013，73（3）：1049-1065.

［16］HE P，YAN B，LIZ，et a1.CM-MAC：A c1uster-based mu1tichanne1MAC Protoco1 for VANET［J］.Journa1 of ComPuter Research &Deve1oPment，2014，51（3）：502-510.

［17］IEEE.IEEE 802.11 Part11：W ire1ess LAN medium access contro1（MAC）and Physica1 1ayer（PHY）sPecifications amendment 8：medium access contro1（MAC）qua1ity of service enhancements［S］.2005.

An inter-c1uster data forwarding scheme for c1uster-based mu1ti-channe1Ad Hoc networks

Wang Di
（Schoo1of Communications and Information Engineering，Nanjing University of Posts and Communications，Nanjing 210003，China）

For the 1arge-sca1e emergency rescue scenario，this PaPer introduces a c1uster-based Ad Hoc network mode1 in order to reduce overheads and faci1itate the network management.It a1so ProPoses amu1ti-channe1hybrid access Protoco1 in order to imProve the channe1uti1ity and increase the network throughPut.And based on this Protoco1，the Prob1ems and the so1utions of nodes communication are discussed，esPecia11y the inter-c1uster communication is introduced detai1ed1y.

Ad Hoc network；mu1tichanne1；c1uster-based structure；inter-c1uster

TN915.9

A

10.19358 /j.issn.1674-7720.2016.09.020

王迪.一种基于多信道分簇结构Ad Hoc网络的簇间中继实现方案［J］.微型机与应用，2016，35（9）：66-69.

20116-01-15）

王迪（1991 -），女，硕士研究生，主要研究方向：下一代网络。