通信学报
通信學報
통신학보
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
2013年
8期
131-139
,共9页
周进怡%夏树涛%江勇%郑海涛
週進怡%夏樹濤%江勇%鄭海濤
주진이%하수도%강용%정해도
多跳无线网络%多流问题%最大吞吐%网络编码%极大独立集搜集算法
多跳無線網絡%多流問題%最大吞吐%網絡編碼%極大獨立集搜集算法
다도무선망락%다류문제%최대탄토%망락편마%겁대독립집수집산법
multihop wireless network%multi-commodity flow problem%maximum throughput%network coding%collect-ing algorithm for maximal independent sets
多流问题研究多对源、宿节点之间所能达到的最大吞吐。在无线网络中,解决该问题的关键在于量化无线干扰。由于网络编码能够在一定程度上克服无线干扰的影响,因此通过使用超边来描述编码发送,并构造关于超边的冲突图,可以实现对网络编码条件下无线干扰(以协议干扰模型为例)的量化,进而解决网络编码条件下的多流问题。此外,针对在超边冲突图中搜集所有极大独立集的NP难问题,提出了一种实用的搜集算法,并给出了相关的数字结果。
多流問題研究多對源、宿節點之間所能達到的最大吞吐。在無線網絡中,解決該問題的關鍵在于量化無線榦擾。由于網絡編碼能夠在一定程度上剋服無線榦擾的影響,因此通過使用超邊來描述編碼髮送,併構造關于超邊的遲突圖,可以實現對網絡編碼條件下無線榦擾(以協議榦擾模型為例)的量化,進而解決網絡編碼條件下的多流問題。此外,針對在超邊遲突圖中搜集所有極大獨立集的NP難問題,提齣瞭一種實用的搜集算法,併給齣瞭相關的數字結果。
다류문제연구다대원、숙절점지간소능체도적최대탄토。재무선망락중,해결해문제적관건재우양화무선간우。유우망락편마능구재일정정도상극복무선간우적영향,인차통과사용초변래묘술편마발송,병구조관우초변적충돌도,가이실현대망락편마조건하무선간우(이협의간우모형위례)적양화,진이해결망락편마조건하적다류문제。차외,침대재초변충돌도중수집소유겁대독립집적NP난문제,제출료일충실용적수집산법,병급출료상관적수자결과。
In a multihop wireless network, wireless interference is crucial to the multi-commodity flow problem, which studies the maximum throughput between multiple pairs of sources and sinks. Based on the observation that network coding (NC) could help to decrease the impacts of wireless interference, a framework was proposed to solve the problem for multihop wireless networks with NC. By introducing hyperarcs to model all possible (uncoded or encoded) transmis-sions and using the conflict graph of hyperarcs to describe the new conflict relations modified by NC (e.g., in the protocol interference model), the problem was formulated to compute the maximum throughput of multiple unicast flows sup-ported by the multihop wireless network with given NC settings, in which the constraints were rebuilt from the conflict graph of hyperarcs. Furthermore, a practical algorithm was proposed to collect maximal independent sets, instead of col-lecting all maximal independent sets in the conflict graph of hyperarcs (which is NP-hard), and some numerical results were illustrated.