一种用于多信道Ad Hoc网络MAC协议的匹配策略  

A Matching Algorithm for Multichannel Ad Hoc Medium Access Control Protocol

作　　者：宋煜[1,2] 左德承[1] 杨孝宗[1] 向琳[1] 

机构地区：[1]哈尔滨工业大学计算机学院 [2]中国人民解放军第65047部队

出　　处：《计算机学报》2012年第5期1018-1030,共13页Chinese Journal of Computers

基　　金：国家预研基金项目(51416040105HT0734);"十一五"部委重点预研项目基金(513160301)和"十一五"部委预研项目基金(513160303)资助~~

摘　　要：在ad hoc网络中,使用多个正交信道,并行地传输数据是一种提高网络吞吐率,降低数据时延的有效手段.目前多广播域类协议,由于不需要额外的硬件,同时也不需要在网络结点之间建立时间同步机制,比其他多信道MAC协议具备更好的灵活性.经过研究发现,传递广播数据包,将加重多广播域协议解决死锁、发送等待和匹配效率等问题的协议开销,从而制约ad hoc网络的实际性能.采用支持广播/多播的匹配策略MAMR(Matching Algo-rithm for Multiple Rendezvous),将有助于解决广播问题.MAMR根据ad hoc网络的数据传送需求,将任一网络收敛至一个无冲突,无死锁的匹配状态.在该策略的收敛状态下所有非广播结点的入度不大于1,并且任两个相邻的广播结点间不会有匹配的边存在,从而避免了广播结点间可能出现的数据发送冲突.进一步证明,该策略可以在O(4m)步内收敛,并且可以在限定条件下达到极大匹配状态;在无广播结点时,该策略与Hsu和Huang提出的分布式网络中的极大匹配策略等价.仿真显示,在具有5%的广播数据需求时,该策略可以使MAXM、BTMC协议性能提高10%.It is effective to increase the throughput and reduce the delay of ad hoc by concurrently transmitting different packets through distinct channels.Compared with other multichannel medium access control（MAC） protocols,Multiple Rendezvous is more flexible since there are no requirements of external hardware and time synchronization.Considering that as the overloads of handling deadlock,waiting and matching increase,the performance of multichannel ad hoc network is reduced by broadcasting,Matching Algorithm for Multiple Rendezvous（MAMR） is proposed.According to broadcast requirements,it is converged to a stable state without collision or deadlock.It has the characteristics that only broadcast nodes＇ degrees are greater than 1,and there exists no edge between broadcast nodes.It is proved that the algorithm stabilizes at most 4m moves on a network with m edges.Under the condition that the set of broadcast nodes is presented before the initial state,a maximal match is reached;under the condition of no broadcast node,the algorithm is equivalent to Hsu and Huang＇s self-stabilizing algorithm for maximal matching.Simulation results show that the performance of MAXimal Matching multichannel（MAXM） and Busy Tone Multichannel（BTMC） protocols are increased by 10% by using MAMR when 5% of transmission packets are required for broadcasting.

关 键 词：多跳分布式无线网络 多址接入协议 广播需求 匹配策略 极大匹配 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]