Ad-Hoc 网络多址接入协议的研究与实现
2008-10-30
作者:王 竞 李建东 盛 敏
摘 要: 在介绍了Ad-Hoc" title="Ad-Hoc">Ad-Hoc网络的概念及特点的基础上,系统地论述了Ad-Hoc网络的多址" title="多址">多址接入技术,总结了适用于现代通信系统的MAC协议所应具备的性能,并对开发Ad-Hoc网络这样一项复工程的方法做了详细的论述。
关键词: Ad-Hoc MAC 无线网络
Ad-Hoc网络是一种无需固定网络作为支撑的网络形式。由于Ad-Hoc网络具有组网快速灵活、抗毁性强、成本低廉等优点,特别适用于军事、抢险救灾、电子教室等领域。这种网络已经成为无线通信领域中一种有效的通信网络形式,而且已经取得了广泛的应用,如802.11系统、美军海陆空一体化数字通信系统。
Ad-Hoc网络可分为Ad-Hoc WLAN(Ad-Hoc Wireless Local Area Network) 和 Mobile Ad-Hoc两类。Ad-Hoc WLAN网络是一种全连通的网络,网络中的任一节点与其它所有节点仅相距一跳范围;Mobile Ad-Hoc 网络,即MANET,是一种非全连通的网络,网络中任意两个节点间的距离大于或等于一跳范围。图1为上述两种网络的拓扑示意图。
1 Ad-Hoc网络的特点
与现有的移动通信网不同,Ad-Hoc网络不依赖固定网络,将地理位置分散的无线电台有效地组织在一起相互通信。由于没有中心基站的支持,组网的重担就落在各个无线电台上,因此这种网络也被称为自组织网。在移动的环境下,各无线电台间的通信链路" title="链路">链路是不固定的,甚至可能发生快速的变化。另外,应用于Ad-Hoc网络的终端设备大多为便携设备或车载设备,设备体积不能很大,且功耗受限,因此这种网络的单跳覆盖范围一般不会很大(军事领域的某些应用可能例外),而且双工方式大多为TDD(时分双工)。
对于Mobile Ad-Hoc网络,拓扑的局部连通性是一个十分重要的特点。正是该特点导致了Ad-Hoc网络中“隐藏终端”的问题。如图1(b)所示,节点A向节点B发送信息时,节点C并不知道,这时如果节点C向B或D发送信息,会导致节点B处信号碰撞,无法正确接收信息。
2 Ad-Hoc网络多址接入协议
自从最早的ALOHA系统诞生以来,Ad-Hoc网络已经经历了30多年的发展历程。以往,Ad-Hoc网络的研究重点主要集中在路由问题,对MAC协议的研究是近年来的热点。早期的Ad-Hoc网络采用的多址接入协议主要是ALOHA协议或CSMA(carrier sense multiple access)协议。由于CSMA协议较ALOHA协议性能优良,而且实现简单,因此取得了广泛的应用。但是,随着通信网络的发展,无论是ALOHA协议还是CSMA协议都显得有些力不从心。下面,就CSMA协议存在的问题进行简要分析。
·CSMA协议的网络通过率与归一化的载波检测时延" title="时延">时延密切相关,其公式如下:
其中,τ为载波检测时延,它由链路的传播时延和物理层的检测时延组成;C为信道传输速率;L为分组长度。由该公式可以发现:随着传播距离的增长、信道速率的提高、分组长度的缩小,β会相应变大。当β达到0.2~0.3,甚至更高时,CSMA这类协议的性能就已经较差了(对于非时隙的CSMA/CD而言,β=0.2时,系统的通过率不足45%),不易再采用CSMA多址接入协议。
·在Mobile Ad-hoc网络中,由于隐藏终端和暴露终端的存在,使得CSMA协议对信道的利用率不高。
·CSMA协议是一种基于'竞争'的多址接入协议,这样的协议无法为每个节点保证传输带宽,分组在网络中的平均时延方差也会因此较大,不适合实时业务或需要QoS保证的业务要求。
近年来,宽带化是通信系统的一个发展方向,而CSMA协议的通过率会随着信道速率的提高有所下降,显然不适合现代通信系统的发展。利用有限的信道资源,尽可能传输更多的信息或者为更多的用户提供服务一直是学者或工程师们追求的目标,而CSMA协议的信道利用率不高,尤其是在Mobile Ad-hoc的网络中,这是无法忍受的。另外,现代通信对多媒体业务的需求已经越来越大,可CSMA协议无法为实时业务(话音业务或视频业务)提供服务,这显然是要被淘汰的。
目前,在学术领域中,Ad-Hoc网络的多址接入协议主要分为两类,即基于竞争的MAC协议和无竞争的MAC协议。前面提到的ALOHA协议和CSMA协议都是基于竞争的MAC协议。由于这种协议在重负载下系统不稳定,导致了无竞争MAC协议的出现。常见的无竞争MAC协议有四类:基于FDMA或TDMA的固定多址协议、基于节点轮循(polling)的协议、基于令牌传递(token passing)的协议、基于动态预约(dynamic reservation)的协议。
在Ad-Hoc网络中,由于节点体积功耗的限制,TDMA协议比FDMA协议更适合。但是,对突发业务模型,TDMA协议会造成较大的信道浪费,而且对于节点数目随时变化的TDMA系统,对时隙的管理会更加复杂。基于节点轮循或令牌传递的协定虽然较TDMA协议避免了许多信道浪费,但是依然存在信道不必要的空闲或信息传输中不必要的延时。在上述情况下,动态预约的多址协议看来会成为最佳的选择。
动态预约的多址协议结合了基于竞争的MAC协议和无竞争的MAC协议的优点。动态预约的对象在目前已有的协议中主要有两类:一类是预约传输分组的权利,另一类是预约调度传输的权利。将这两类协议分别标记为第一类DR-MAC协议和第二类DR-MAC协议。
第一类DR-MAC协议比较典型的有:MACA、MACAW、FAMA、802.11、RAMA、BB Contention等。这类协议的基本思想都是节点在传输前通过RTS/CTS握手信号预约信道,预约到后,再无冲突传输。如图1(b)所示,A向B发送信息前,先发出RTS预约分组,B收到RTS分组后,应答CTS分组,允许发送。同时A的隐藏终端C也可得到通知,于是在A向B发送信息期间,C不会发送信息,AB间的信息传输自然是无冲突的。第一类DR-MAC协议的区别在于如何应对RTS分组的碰撞。例如MACA协议采用基于分组帧听的方法,而FAMA协议采用基于载波帧听的策略。第二类DR-MAC协议有DQRAP、CARMA-NTG、GAMA等。
近年来,如何在Ad-Hoc网络中采用动态预约的TDMA协议一直是一个研究热点。由于这种协议预约的同样是传输分组的权利,因此将其也归为第一类DR-MAC协议。这样的协议有:D-TDMA、E-TDMA、FPRP等。这些协议关注的焦点都是如何预约信道,不同的预约策略可为业务提供不同的服务质量,占用的信道开销当然也不会相同。然而,对于Ad-Hoc网络,如何实现全网同步是实现上述系统的难点所在。从全网同步的角度出发,又可将Ad-Hoc网络分为有中心的网络和无中心的网络。对于有中心的网络,所有节点都与中心节点直接相连,因此全网的同步信息可由中心节点发布,其它节点都以中心节点为基准,与其保持时隙同步。对于无中心的网络(大多数的Mobile Ad-hoc网络都是无中心的)如何实现全网同步一直是一个难点。目前解决该问题的主要方法是以GPS定时信号为基准,实现网内各节点的粗同步,再通过对训练序列相关运算寻找相关峰,计算定时偏差,并自适应调整实现节点间的精确同步。
通过对上述多址接入协议的研究可以看到,用于Ad-Hoc网络的多址接入协议应具备如下特点:
·协议要能够适应拓扑的动态变化,即自适应拓扑变化;
·协议要能够适应不同业务对带宽的需求,保证业务的服务质量QoS,即自适应业务变化;
·协议要能够为不同优先级的业务提供不同的服务质量QoS(如紧急业务的优先级要高于实时业务,实时业务的优先级要高于非实时业务);
·协议要尽可能地避免信道的碰撞和不必要的空闲,同时减小控制开销,提高对信道的利用率。
3 Ad-Hoc网络多址协议的开发
对无线通信网络的开发是一个复杂的工程,尤其是在条件有限的实验室内。笔者的开发思想如图2所示。
整个通信网络开发平台" title="开发平台">开发平台由MAC协议开发平台、物理层模拟平台和信道模拟器三部分组成。通信软件开发平台和物理层模拟平台合为一个节点平台。
3.1 MAC协议开发平台
MAC协议开发平台主要由嵌入式微处理器、存储系统及相关各种接口组成。对该平台的设计主要集中在嵌入式微处理器的选型上。在这里,笔者最关心的是处理器的处理速度能否满足系统参数的需求。虽然,各种处理器都提供了相关的处理能力指标(如ARM9处理器在200MHz的频率下,处理能力为220MIPS)给用户以参考,但是最终的软件执行时间还与软件自身的设计及编译器的编译效率等因素有关。因此,这个问题很难有一个明确的结论。
笔者在设计中采用了ARM处理器运行MAC协议软件。对ARM处理器的选择是通过下述方法确定的。首先,设计并编写处理时间敏感的软件,然后在AXD调试工具下调用ARMUL调试内核,对编写的软件进行实时分析。在调用ARMUL调试内核时,应根据使用处理器的特点(如是否带有MMU功能)、系统的时钟频率、存储器的访问时间等相关参数进行设置。运行软件时,调用Debugger Internals工具,就可以看到运行整个软件所需要的时钟周期及对总线上各种时序的统计。由此可以判断这部分软件的运行时间,以及选择处理器能否满足需要。另外,在选择处理器时,应注意给处理器留下一定的余量(一般,应留下30%的处理余量)。
3.2 物理层模拟平台
物理层模拟平台主要由FPGA实现。该平台可作为一个设备直接挂在上述处理器的总线上,也可以通过串口、USB口或其它接口与MAC协议开发平台相连。这应根据实际工程需要选择,笔者选择的是前者。物理层模拟器的平台框图如图3所示。
对信道的模拟采用5线制,分别是:发送数据线、接收数据线、发送指示线、接收指示线和地线。将发送数据线和接收数据线分开,是为了避免模拟碰撞事件发生时可能造成的对器件的损坏(例如将两个节点对连,且同时发送数据的情况)。由于收发数据线只有“0”或“1”这两种状态,无法区分信道有无数据,因此增加了收发指示线。同时,通过这两条线可以方便处理器判断信道是否发生碰撞。
在物理层设置2个发送缓存和2个接收缓存可以提高协议的性能。MAC层与物理层的数据交换采用“乒乓”方式,即当物理层操作缓存A时,MAC层可操作缓存B,这样MAC层与物理层的数据交换就不会占用信道时间。
3.3 信道模拟器
因为是对链路层的通信模拟,所以物理信道的多径干扰、同道干扰等因素可以完全忽略掉。而在Ad-Hoc网络中,通信链路的那些特点会对MAC层及高层的处理造成影响。总结出如下几点:
·传播时延;
·随机错误(对于突发错误,完全可以通过交织技术离散为随机错误);
·网络拓扑的动态变化。
信道模拟器可由FPGA和单片机实现,所需要模拟的链路事件有:传播时延、信道碰撞、信道出错、拓扑改变。
对传播时延的模拟可由移位寄存器完成,移位寄存器的输入时钟等于信道波特率,移位寄存器的级数可由单片机动态控制。对信道碰撞的模拟可由逻辑与门(或逻辑或门)和收发状态指示线共同完成。对信道出错的模拟可由单片机运行与实际信道特性相符的随机错误产生算法,改变移位寄存器上某一位或某几位的状态来实现。网络拓扑的改变可由单片机控制,按预先设置或按键输入动态改变。
4 几点说明
(1)对MAC层的协议设计与物理层及工作的物理环境是密不可分的。因此,在开发MAC层协议及软件时,对物理层模拟平台的设计和信道模拟器的设计应根据系统的最终工作环境及相关系统参数设计。
(2)按照上述开发方法所开发的MAC层软件可直接应用于最终的系统上。按照这样的思路,各通信层面上的软件开发都可通过建立相应的链路模拟平台来并行开发,缩短开发周期。
(3)在对处理器的选择的讨论中没有考虑操作系统的影响。如果考虑操作系统,那么处理器的处理能力按照经验只能折算为以前的1/3。
(4) 如果需要开发的系统是全网同步的,如TDMA系统,那么物理层模拟器的设计将更为复杂。
参考文献
1 李建东. 信息网络理论基础.西安:西安电子科技大学出版社
2 Mort Naraghi-Pour, Ph.D. Investigation of Media Access Control Protocols for Mobile Ad-hoc Networks
3 Andrew Muir and J.J.Garcia-Luna-Aceves. An Efficient Packet Sensing MAC Protocol for Wireless Networks