基于时隙泛洪的无路由移动无线自组网协议及其扩展方法*

赖增桂，蔡雪梅，李默嘉

0 引 言

移动无线自组网（MANET）可满足无基础设施情况下的通信需求，是无线通信领域中的热点研究问题[1-2]，在应急、军事等特殊领域具有广泛的应用前景。但是，传统的MANET网络都具有复杂庞大的协议体系，尤其是其路由协议，给原本带宽较窄、链路不稳定的无线传输链路造成了较大负担。当网络动态性较大（拓扑变化快）时，路由协议的控制开销会急剧增加，从而增加网络拥塞度，降低网络工作效率，导致网络不能够较好地为用户提供稳定可靠的通信服务。

针对庞大的自组网协议体系尤其是路由协议导致额外无线传输开销的问题，本文提出一种无需单独的路由协议，基于链路层时隙泛洪的移动无线自组网的网络协议，提出了一种提升信道利用率、增加用户容量的优化方法，以及基于该协议的通用自组网协议扩展方法。

1 协议基本原理

1.1 要求及假设

本文设计的协议适用的无线信道需要具备以下特点和能力：

（1）无线信道采用同步工作方式，其时钟同步可采用外时钟同步，如高精度高稳时钟、卫星定位系统时钟（如北斗、GPS）等，或者借助物理层方法进行互同步或主从同步，如基于同步头和时间信息TOD的跳频同步[3-4]；

（2）无线信道为全向广播信道，在定向无线信道下的协议扩展需进一步研究；

（3）无线信道设备需具备足够快的收发切换和收发处理能力，以确保网络性能；

（4）无线信道设备需要具备能够接收处理并利用多径信号的能力。

为后续描述准确方便，对MANET网络的性能进行如下假设：

（1）网络支持的最大用户数为M，每一个用户均有一个[0，M-1]内唯一的标识ID；

（2）网络支持的最大中继跳数为N。

1.2 帧结构

网络的最小时间单元为时隙，所有时隙的长度均一致且固定，N个时隙构成一个时帧，M个时帧构成一个时元。一个时元是网络运行的一个基本周期，其帧结构如图1所示。

图1 帧结构

1.3 时帧/时隙的分配与使用

时帧采用固定为每个用户分配的方式。网络内的每个用户节点都按照标识ID分别分配1个时帧作为自己的时帧，如标识ID为0的用户分配0号时帧。用户将自己时帧内的第0时隙作为自己的源信息（该用户节点发起的信息）发送时隙。所有的用户节点都按照如下方法使用时帧和时隙：

（1）当某用户节点有源信息需要发送时，在该用户节点的时帧的0时隙（也就是源信息发送时隙）对源信息进行发送，发送后该节点在本时帧周期内的后续时隙进入休眠状态（不再接收处理和发送任何信息数据），直到下一时帧周期开始才唤醒（重新开始收发工作）；

（2）当一个节点在不属于自己的时帧内的n（n＜N-1）时隙收到了信息，则需判断该信息的目的节点是否为本节点。若为本节点，则进行接收处理；否则，该节点立即在该时帧内的n+1时隙转发该信息。完成转发后，该节点在本时帧周期内的后续时隙进入休眠状态，直到下一时帧周期开始才唤醒；

（3）当一个节点在不属于自己的时帧内的n（n＜N-1）时隙收到了信息，则判断该信息的目的节点是否为本节点，若为本节点，则进行接收处理，否则丢弃该信息。

在上述时帧/时隙的使用过程中，信息的接收和转发行为之间，涉及到无线信道的收发转化时间、收发处理时延以及无线传播时延等时延因素。为确保数据能够正确收发和处理，需要在不同时隙间预留时隙间保护时间。时隙间保护时间越短，对网络性能影响越小。所以，要求无线信道需具备足够快的收发切换和收发处理能力，以确保网络性能。

另外，在上述使用过程中会遇到如下类多径情况。如图2所示拓扑，当A节点有信息需要发送时，在某时隙进行了发送，B、C节点都会收到并进行转发，D节点则会同时收到来自B、C节点转发的信息，则D节点需要同时处理来自两条不同路径的相同信号，所以要求无线信道需要具备能够接收处理并利用多径信号的能力。

图2 类多径拓扑

1.4 协议总结

上述协议具有如下特点：

（1）一个时帧内每个节点最多只在某一个时隙内进行数据发送（包括源数据的发送和其他节点数据的转发），其他时隙要么处于接收状态要么处于休眠状态；

（2）一个时元内某个节点只有一个时隙（也就是本节点时帧的0时隙）能够进行本节点源数据的发送，所以在不考虑时隙间保护时间的情况下，每个节点的有效数据速率是信道速率的1/(M×N)；

（3）通过多跳基于时隙泛洪的方式，无需路由协议的支撑，任何节点发送的数据均能被N跳范围内的目的节点正确接收。

1.5 协议性能分析计算及应用场景推荐

以信道速率R=4 Mb/s、用户数M=16、最大支持跳数N=4计算，则单个用户有效速率为4 Mb/s/(16×4)= 64 kb/s。假设网络信息的传输时延要求为10 ms，则时元周期可设置为10 ms，时帧周期为10 ms/16= 625 μs，每个时隙为625 μs/4=156.25 μs，每个用户节点一个时元周期内最多可传递4 Mb/s×156.25 μs≈640 bit（即80 Byte）数据（注：以上计算忽略时隙间保护时间）。

通过分析计算可以看出，该组网协议适用于节点分布较密集（转发跳数少）、节点信息量较固定、节点移动性较强（网络拓扑变化快）、对传输时延较敏感的场合，如分队级别的火力协同网络、区域范围内的车联网络等。它最适合的应用业务是子网广播，尤其是全子网的话音广播。

2 协议性能优化措施

2.1 优化思路

前述协议的时帧/时隙的分配采用固定分配的方法，导致网络对信道资源的利用率相对较低。同时，固定分配的方式直接限定了用户数量，不利于网络的扩展，无法实现少量临时用户的加入。此外，由于所有用户的时帧分配都是相同的，无法满足高优先级用户的更高要求的通信需求。针对以上问题和不足，提出基于时隙CSMA/CA[5]方式接入的性能优化方法。

2.2 优化改进措施

时帧/时隙的分配不再针对每个用户进行固定分配，而是所有的用户共享所有时帧。需要使用时帧/时隙的用户采用载波侦听多址随机接入/冲突避免（CSMA/CA）的方式竞争使用。当一个节点有源数据需要发送时，首先侦听当前时帧0时隙是否空闲。若空闲，则占用该时隙发送源数据；若被占用，则随机退避x个时帧重新侦听0时隙进行接入发送。当一个节点在某时帧的y时隙有转发数据需要发送时，则侦听该时帧的y+1时隙是否空闲。如空闲，则转发；若被占用，则监听该时帧的y+1时隙。重复，直到占用某时隙转发或直到该时帧的N-1时隙为止。

需要注意的是，采用时隙CSMA/CA接入方式后，CSMA接入协议固有的“隐藏终端”问题和“暴露终端”问题[6-7]将被引入。如图2所示拓扑，若A、D节点同时发送，B、C节点均无法正确接收并转发数据，即引入了“隐藏终端”问题。同样，当C、D节点同时有数据发送时，则会引入“暴露终端”问题，原本可以同时发送的C、D节点由于“暴露终端”问题，导致必须进行相应的退避操作，降低信道利用率。另外，由于多跳泛洪转发的原因，2跳甚至多跳外时帧复用后引入的“多跳隐藏终端”和“多跳暴露终端”问题也会随之产生。但是，复杂拓扑下借助多跳泛洪转发机制，可解决部分“隐藏终端”和“暴露终端”问题，如图3所示拓扑。当A、D节点同时发送源数据时，虽然B、C由于冲突的原因无法在第一时间（当前时隙）正确接收并转发，但是E节点收到A信息后进行转发，C节点可以正确接收并转发；D节点信息经G、F节点接收并转发后，B节点能够正确接收并转发，C转发A信息和B转发D信息不在同一时隙，A、D的接收不会产生冲突，可以实现全网的正确传输。

图3 “隐藏终端”问题解决方法

2.3 优化后性能分析

优化后，网络开通后增加少量的用户不再需要重新进行设计和规划。新增加的用户开机即可正常接入并使用网络。同时，有更多业务传输需求的高优先级用户可以占用更多的时帧用于源数据发送，提升了传输带宽。

经Opnet仿真，网络用户数为16，每个用户均以≤64 kb/s的速率产生业务。在协议未经优化时，网络收发的业务量如图4所示（“Traffic Sink.Traffic Sent(packets)”表示网络发送的数据报文总数量，“Traffic Sink.Traffic Receibed(packets)”表示网络接收的数据报文总数量，纵轴表示报文数量，横轴表示仿真时间），网络传输时延如图5所示（纵轴表示每个报文的传输时延，横轴表示仿真时间）。从图4、图5可以看出，在协议未经优化时，网络的收发数据量保持一致，即网络的业务递交率达到100%，所有业务的传输时延均控制在10 ms以内。

图4 固定用户数量（16）的收发业务量

图5 固定用户数量（16）的传输时延

进行协议优化后，网络用户数分别设置为16、32、64、128。所有用户以泊松分布的方式共产生≤4 Mb/s的业务。冲突时，随机退避时间范围固定为16个时帧周期，网络的业务递交率如图6所示（不同线条表示不同用户数情况下的业务递交率，纵轴表示递交概率，横轴表示仿真时间），传输时延如图7所示（四种用户数量下的传输时延，纵轴表示传输时延，横轴表示仿真时间）。从图6、图7可以看出，协议进行优化后，随着用户数的增加，其业务的递交率没有明显变化，传输时延也基本保持不变（10 ms以内），即优化的协议通过牺牲较少的递交率可以换取更多用户的随遇接入。

图6 不同用户数量的递交率

图7 不同用户数量的传输时延

3 协议扩展

上述协议的使用范围相对较固定，适用的场景局限于以时敏广播通信为主的网络。而对于业务传输需求较随机的用户组成的网络，它的使用不够灵活，网络应用效率也不够高。因此，可以针对以上协议进行扩展，以适应以随机通信（通信的源和目的随机、通信业务的大小随机、通信的时间随机）为主的网络。将MANET网络内较固定且时延要求敏感的组网控制信息（如路由信息、资源分配信息等）使用上述协议进行传输，其他资源进行灵活分配，以提升网络应用的普适性和网络的应用效率。

下文针对以上需求设计了一种典型的扩展协议。将第2节设计的时元作为网络的控制时隙用作组网控制信息的传递，后续紧跟K个业务时隙用做业务传输，形成如图8所示的帧结构。

图8 扩展超帧结构

其中，控制时隙中的时帧/时隙的使用方式如1.3节所述，业务时隙的分配使用根据后续组网控制协议和算法分配使用。

控制时隙中，每个节点需要广播的源控制信息内容包括：源节点的唯一标识ID（长度为logM比特）和邻居状态（长度为M比特）。通过此协议，在两个超帧周期内即可快速完成网络的自组织收敛。

第一个超帧周期中，在本节点时帧的0时隙发起源控制信息泛洪，初始状态仅携带本节点的ID，其余比特全为0；在X时帧的0时隙接收到泛洪，则置X节点为邻居，邻居状态的相应比特位（X比特位）置为1。

第二个超帧周期中，在本节点时帧的0时隙发起控制信息泛洪。信息包含本节点ID和上一超帧周期内收集的邻居状态。通过全网泛洪邻居状态，网内所有节点均可以获取全网拓扑。根据全网拓扑即可完成全网路由计算（推荐路由计算算法采用最短路径算法[8-9]）；根据全网拓扑和业务时隙实际情况即可完成时隙分配（时隙分配算法可考虑采用着色算法[10]，更优时隙分配算法另文讨论），从而完成网络自组织。

4 结 语

本文设计了一种适用于业务传输时延敏感、用户快速移动、用户业务量较固定等应用需求的简单无线自组网协议，采用基于时隙泛洪的方式屏蔽了对自组网路由协议的依赖，大大简化了网络协议体系，提升了网络运行稳定度。此外，针对标准自组织网络的组网控制信息特点，以此协议为基础，对协议进行扩展，形成两个超帧周期即可实现网络收敛的自组网协议。

[1] Nieminen K.Introduction to Ad Hoc Networking [D].Helsinki:Networking Laboratory Helsinki University of Technology,2003.

[2] Colagrosso M D.Intelligent Broadcasting in Mobile ad Hoc Networks:Three Classes of Adaptive Protocols[J].EURASIP Journal on Wireless Communication and Networking,2007,2007(01):16.

[3] 张远贵,向新,梅文华等.一种基于时间信息TOD的跳频同步方法[J].现代电子技术.2009(02):82-84.ZHANG Yuan-gui,XIANG Xin,MEI Wen-hua,et al.Synchronization Scheme for Frequency Hopping Communication System Based on Time of Day[J].Modern Electronic Technology,2009(02):82-84.

[4] 刘雪峰.高速/变速跳频同步技术[J].计算机与网络,2009(09):38-40.LIU Xue-feng.Technique of High/Variable Speed Frequency Hopping Synchronization[J].Computer and Networks,2009(09):38-40.

[5] Koubaa A,Alves M,Nefzi B,et al.Improving the IEEE 802.15.4 Slotted CSMA/CA MAC for Time-critical Events in wireless sensor networks[C]//Proceedings of the Workshop of Real-Time Networks，2006：1-6.

[6] 任远,董淑福,王耀国.数据链中隐藏终端问题的几种解决方法[J].通信技术.2009,42(09):54-56.REN Yuan,DONG Shu-fu,WANG Yao-guo.Some Solutions for Problem of Hidden Terminal in Data Link[J].Communications Technology,2009,42(09):54-56.

[7] 兰丽,单志龙.Ad Hoc网络中隐藏终端和暴露终端相关问题研究[J].计算机与数字工程,2010,38(07):36-40.LAN Li,SHAN Zhi-long.Analysis on Relevant Problems of Hidden Terminal and Exposed Terminal in Ad Hoc Networks[J].Computer & Digital Engineering,2010,38(07):36-40.

[8] DEO N,PANG C Y.Shortest Path Algorithms:Taxonomy and Annotation[J].Networks,1984(14):275-323.

[9] CHERKASSKY B V,GOLDERG A V,RA DZIKT.Shortest Paths Algorithms:Theory and Experimental Evaluation[J].Mathematical Programming,1996(73):129-174.

[10] 孙彦赞,姜玉凤,吴雅婷等.基于改进式随机不完全着色算法的无线体域网干扰协调[J].电子与信息学报,2015,37(09):2204-2210.SUN Yan-zan,JIANG Yu-feng，WU Ya-ting，et al.Improved Random Incomplete Coloring for Interference Mitigation in Wireless Body Area Networks[J].Journal of Electronics & Information Techno logy,2015,37(09):2204-2210.