软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2013年
6期
1295-1309
,共15页
肖春静%刘明%龚海刚%陈贵海%周帆%吴跃
肖春靜%劉明%龔海剛%陳貴海%週帆%吳躍
초춘정%류명%공해강%진귀해%주범%오약
无线Mesh网络%组播%最小干扰组播树%信道分配
無線Mesh網絡%組播%最小榦擾組播樹%信道分配
무선Mesh망락%조파%최소간우조파수%신도분배
wireless mesh network%multicast%minimum interference multicast trees%channel assignment
不同于无线传感器网络和移动Ad Hoc网络,无线Mesh网络中的组播主要侧重于提高吞吐量,而干扰是影响吞吐量的重要因素。在构建组播拓扑时,传统的方法主要考虑最小价值或最短路径,而通过减少干扰来提高组播性能的研究较少,且它们的干扰计算方法都采用单播的思想,并不适合于组播。例如,当n个接收节点同时从一个节点接收数据时,在组播中这n个接收节点之间不存在干扰,而在单播中认为存在干扰。因此,提出了组播冲突图来计算组播干扰,给出组播树干扰的定义。可以发现,求最小干扰组播扰树是NP完全问题,然后提出基于万有引力的启发式算法构建具有较小干扰的组播树。为了适用于多信道的情况,提出了满足不同干扰范围的多跳信道分配算法。最后,仿真结果显示,与MCM相比,所提出的算法无论是在单天线单信道还是多天线多信道下,都能取得较高的吞吐量和较低的延迟。
不同于無線傳感器網絡和移動Ad Hoc網絡,無線Mesh網絡中的組播主要側重于提高吞吐量,而榦擾是影響吞吐量的重要因素。在構建組播拓撲時,傳統的方法主要攷慮最小價值或最短路徑,而通過減少榦擾來提高組播性能的研究較少,且它們的榦擾計算方法都採用單播的思想,併不適閤于組播。例如,噹n箇接收節點同時從一箇節點接收數據時,在組播中這n箇接收節點之間不存在榦擾,而在單播中認為存在榦擾。因此,提齣瞭組播遲突圖來計算組播榦擾,給齣組播樹榦擾的定義。可以髮現,求最小榦擾組播擾樹是NP完全問題,然後提齣基于萬有引力的啟髮式算法構建具有較小榦擾的組播樹。為瞭適用于多信道的情況,提齣瞭滿足不同榦擾範圍的多跳信道分配算法。最後,倣真結果顯示,與MCM相比,所提齣的算法無論是在單天線單信道還是多天線多信道下,都能取得較高的吞吐量和較低的延遲。
불동우무선전감기망락화이동Ad Hoc망락,무선Mesh망락중적조파주요측중우제고탄토량,이간우시영향탄토량적중요인소。재구건조파탁복시,전통적방법주요고필최소개치혹최단로경,이통과감소간우래제고조파성능적연구교소,차타문적간우계산방법도채용단파적사상,병불괄합우조파。례여,당n개접수절점동시종일개절점접수수거시,재조파중저n개접수절점지간불존재간우,이재단파중인위존재간우。인차,제출료조파충돌도래계산조파간우,급출조파수간우적정의。가이발현,구최소간우조파우수시NP완전문제,연후제출기우만유인력적계발식산법구건구유교소간우적조파수。위료괄용우다신도적정황,제출료만족불동간우범위적다도신도분배산법。최후,방진결과현시,여MCM상비,소제출적산법무론시재단천선단신도환시다천선다신도하,도능취득교고적탄토량화교저적연지。
Compared with wireless sensor networks and mobile ad hoc networks, wireless mesh networks mainly focus on improving the throughput of multicast, while interference severely limits the network throughput. When building a multicast topology, the minimum cost or shortest path is generally taken into account in the traditional methods, and only a few works have tried to improve the performance by reducing interference. However, they calculate the interference by the method for unicast topology, which is not suitable for multicast. For example if n nodes will receive simultaneously packets from one node, among these n nodes there is interference in unicast, but not in multicast. Therefore this tudy proposes the multicast conflict graph to calculate interference of the multicast topology, and then the concise definition of interference of multicast trees is provided. The study shows that building minimum interference multicast trees (MITs) is a NP-complete problem and proposes a gravitation-based heuristics to approximate such optimal trees. To apply to the environment of multi-channel, the study also proposes the multi-hop channel algorithm (MH) for multicast, which can meet different interference ranges. Simulation results reveal that the algorithms can reduce interference and increase throughput in both single-interface single-channel and multi-interface multi-channel wireless mesh networks.