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

doi:10.3969/j.issn.1000-436x.2013.08.017

通信学报 ›› 2013, Vol. 34 ›› Issue (8): 131-139.doi: 10.3969/j.issn.1000-436x.2013.08.017

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

周进怡,夏树涛,江勇,郑海涛

清华大学深圳研究生院，深圳 518055

出版日期:2013-08-25 发布日期:2017-08-31
基金资助:
国家自然科学基金资助项目;高等学校博士学科点专项科研基金资助项目;东南大学移动通信国家重点实验室开放研究基金资助项目

Research on multiflow in wireless networks based on network coding

Jin-yi ZHOU,Shu-tao XIA,Yong JIANG,Hai-tao ZHENG

Graduate School at Shenzhen,Tsinghua University,Shenzhen 518055,China

Online:2013-08-25 Published:2017-08-31
Supported by:
The National Natural Science Foundation of China;The Research Fund for the Doctoral Program of Higher Education of China;The Open Research Fund of National Mobile Communications Research Laboratory,Southeast University

摘要/Abstract

摘要：

多流问题研究多对源、宿节点之间所能达到的最大吞吐。在无线网络中，解决该问题的关键在于量化无线干扰。由于网络编码能够在一定程度上克服无线干扰的影响，因此通过使用超边来描述编码发送，并构造关于超边的冲突图，可以实现对网络编码条件下无线干扰（以协议干扰模型为例）的量化，进而解决网络编码条件下的多流问题。此外，针对在超边冲突图中搜集所有极大独立集的NP难问题，提出了一种实用的搜集算法，并给出了相关的数字结果。

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

Abstract:

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 supported 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.

Key words: multihop wireless network, multi-commodity flow problem, maximum throughput, network coding

周进怡,夏树涛,江勇,郑海涛. 基于网络编码的无线网络多流问题研究[J]. 通信学报, 2013, 34(8): 131-139.

Jin-yi ZHOU,Shu-tao XIA,Yong JIANG,Hai-tao ZHENG. Research on multiflow in wireless networks based on network coding[J]. Journal on Communications, 2013, 34(8): 131-139.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 11

[12]	AHUJA R K , MAGNANTI T L , ORLIN J B . Network flows:Theory,Algorithms,and Applications[M]. New Jersey,USA: Prentice Hall, 1993.
[13]	IBM ILOG CPLEX optimizer[EB/OL]. . 2012.
[1]	CHAVTAL V . Linear Programming[M]. New York,USA: W H Freeman and Company, 1983.
[2]	JAIN K , PADHYE J , PADMANABHAN V N ,et al. Impact of interference on multi-hop wireless network performance[J]. ACM/Springer Wireless Networks, 2005,11: 471-487.
[3]	AHLSWEDE R , CAI N , LI S R ,et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.
[4]	KATTI S , RAHUL H , HU W ,et al. XORs in the air:practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008,16(3): 497-510.
[5]	GUPTA P , KUMAR P R . The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000,46(2): 388-404.
[6]	WAN P J . Multiflows in multihop wireless networks[A]. ACM MOBIHOC[C]. New Orleans,USA, 2009. 85-94.
[7]	CHAPORKAR P , PROUTIERE A . Adaptive network coding and scheduling for maximizing throughput in wireless networks[A]. ACM MOBICOM[C]. Montreal,Canada, 2007. 135-146.
[8]	LIU J , GOECKEL D , TOWSLEY D . Bounds on the gain of network coding and broadcasting in wireless networks[A]. IEEE INFOCOM[C]. Anchorage,USA, 2007. 724-732.
[9]	SENGUPTA S , RAYANCHU S , BANERJEE S . An analysis of wireless network coding for unicast sessions:the case for coding-aware routing[A]. IEEE INFOCOM[C]. Anchorage,USA, 2007. 1028-1036.
[10]	LE J , LUI J , CHIU D M . How many packets can we encode? - an analysis of practical wireless network coding[A]. IEEE INFOCOM[C]. Phoenix,USA, 2008. 371-375.
[11]	GAREY M R , JOHNSON D S . Computers and Intractability:a Guide to the Theory of NP Completeness[M]. New York,USA: W H Freeman and Company, 1979.

[1]	赖恪, 雷菁, 刘伟, 文磊. 基于网络编码的稀疏码分多址接入HARQ方案[J]. 通信学报, 2022, 43(9): 57-69.
[2]	杨君一, 李博, 张钦宇. 基于物理层网络编码的无人机中继网络资源优化[J]. 通信学报, 2021, 42(9): 12-20.
[3]	刘光军, 郭网媚, 熊金波, 刘西蒙, 董长宇. 适用于再生编码分布式存储的轻量型隐私保护审计方案[J]. 通信学报, 2021, 42(7): 220-230.
[4]	李陶深, 孙莉, 王哲. 源节点电池容量受限的菱形信道最优传输策略[J]. 通信学报, 2021, 42(6): 158-170.
[5]	殷俊, 沙雪琪, 王磊, 张登银, 杨余旺. 基于网络编码的协作恢复机制线性可解性研究[J]. 通信学报, 2021, 42(5): 216-229.
[6]	蒲保兴,莫智懿. 双单播网络编码的构造方法[J]. 通信学报, 2020, 41(9): 92-103.
[7]	俞惠芳,李雯. 单/多源网络编码同态签名方案[J]. 通信学报, 2019, 40(11): 112-121.
[8]	陈越,王龙江,严新成,张馨月. 基于再生码的拟态数据存储方案[J]. 通信学报, 2018, 39(4): 21-34.
[9]	肖帅芳,郭云飞,黄开枝,金梁. 面向物联网多跳中继系统的协作密钥生成方法[J]. 通信学报, 2018, 39(3): 86-94.
[10]	吴昊,赖成喆,范九伦,刘建华. 云环境下基于安全网络编码的数据更新算法[J]. 通信学报, 2017, 38(5): 121-127.
[11]	王龙江,陈越,严新成,黄恺翔. 网络编码云存储系统差分数据更新方案[J]. 通信学报, 2017, 38(3): 154-164.
[12]	高锐锋,吉晓东,包志华,张士兵,徐晨. 多中继去噪重传物理层网络编码自适应分集策略[J]. 通信学报, 2017, 38(2): 81-93.
[13]	王棋萍,魏祥麟,范建华,王统祥,胡飞. 面向多跳无线网络的多干扰源定位算法[J]. 通信学报, 2016, 37(12): 176-186.
[14]	陈志刚,沈小建,刘立. 无线mesh网中最小编码代价低时延多播路由[J]. 通信学报, 2016, 37(1): 10-16.
[15]	尚凤军,龚文娟,耿哲. 基于链路预测和网络编码的MAC机制[J]. 通信学报, 2016, 37(1): 17-27.

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

Research on multiflow in wireless networks based on network coding

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 11

相关文章 15

Metrics

推荐阅读 0