基于网络编码的无线网络多流问题研究  

Research on multiflow in wireless networks based on network coding

作　　者：周进怡[1] 夏树涛[1] 江勇[1] 郑海涛[1] 

机构地区：[1]清华大学深圳研究生院,深圳518055

出　　处：《通信学报》2013年第8期131-139,共9页Journal on Communications

基　　金：国家自然科学基金资助项目(60972011);高等学校博士学科点专项科研基金资助项目(20100002110033);东南大学移动通信国家重点实验室开放研究基金资助项目(2011D11)~~

摘　　要：多流问题研究多对源、宿节点之间所能达到的最大吞吐。在无线网络中,解决该问题的关键在于量化无线干扰。由于网络编码能够在一定程度上克服无线干扰的影响,因此通过使用超边来描述编码发送,并构造关于超边的冲突图,可以实现对网络编码条件下无线干扰(以协议干扰模型为例)的量化,进而解决网络编码条件下的多流问题。此外,针对在超边冲突图中搜集所有极大独立集的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） transmissions 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 collecting all maximal independent sets in the conflict graph of hyperarcs （which is NP-hard）, and some numerical results were illustrated.

关 键 词：多跳无线网络 多流问题 最大吞吐 网络编码 极大独立集搜集算法 

分 类 号：TN92[电子电信—通信与信息系统]