D2D网络中基于截止时间约束的网络编码重传方法
|
摘要
最近研究表明,结合D2D与网络编码技术可以显著地提高无线网络的吞吐量。对于视频直播、在线游戏等实时应用而言,通常数据包的接收具有截止时间限制,超出该时间限制的数据包对用户来说是无效的。为最大化用户可及时接收的数据包数量,提出了基于截止时间约束的网络编码(IDNC)重传方法。首先,将问题建模为整数线性规划问题,并证明了这是一个NPhard的问题。其次,为降低求解的复杂度与计算量,构造了IDNC图,用于表示满足截止时间约束的编码组合,并提出了高效的最大权重团搜寻算法。最后,仿真验证了所提方法的有效性。
Recent studies have shown that combining D2D with network coding techniques can significantly increase the throughput of wireless networks. For real-time applications such as live video,online games,etc.,usually the reception of packets has strict delay constraint,and the packets beyond the deadline are invalid for the user. In order to maximize the number of packets that users can receive in time,this paper proposes a deadline constrained retransmission method based on instantly decodable network coding( IDNC). We firstly formulate the problem with integer linear programming,and then prove that it is NP-hard. Secondly,in order to reduce the complexity and computational complexity of the solution,this paper constructs an IDNC graph to represent all feasible coding opportunities,and proposes an efficient maximal weight clique search algorithm. Finally,simulation results demonstrate the superiority of our proposed method.
Recent studies have shown that combining D2D with network coding techniques can significantly increase the throughput of wireless networks. For real-time applications such as live video,online games,etc.,usually the reception of packets has strict delay constraint,and the packets beyond the deadline are invalid for the user. In order to maximize the number of packets that users can receive in time,this paper proposes a deadline constrained retransmission method based on instantly decodable network coding( IDNC). We firstly formulate the problem with integer linear programming,and then prove that it is NP-hard. Secondly,in order to reduce the complexity and computational complexity of the solution,this paper constructs an IDNC graph to represent all feasible coding opportunities,and proposes an efficient maximal weight clique search algorithm. Finally,simulation results demonstrate the superiority of our proposed method.
引文
[1]Cisco.Cisco visual networking index:global mobile data traffic forecast update(2016-2021)[R].2017.
[2]GAO C,LI Y,ZHAO Y,et al.A two-level game theory approach for joint relay selection and resource allocation in network coding assisted D2D communications[J].IEEE Transactions on Mobile Computing,2017,16(10):2697-2711.
[3]DOUIK A,SOROUR S,AL-NAFFOURI T,et al.Instantly decodable network coding:from centralized to device-to-device communications[J].IEEE Communications Surveys&Tutorials,2017,19(2):1201-1224.
[4]AHLSWEDE R,CAI N,LI S Y R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
[5]CHATZIGEORGIOU I,TASSI A.Decoding delay performance of random linear network coding for broadcast[J].IEEE Transactions on Vehicular Technology,2017,66(8):7050-7060.
[6]牛腾,张冬梅,许魁,等.最小化重传次数的无线网络编码广播重传算法[J].信号处理,2017(10):1368-1376.
[7]ABOUTORAB N,SADEGHI P,TAJBAKHSH S E.Instantly decodable network coding for delay reduction in cooperative data exchange systems[C].IEEE International Symposium on Information Theory Proceedings.IEEE,2013:3095-3099.
[8]DOUIK A,SOROUR S,AL-NAFFOURI T Y,et al.Instantly decodable network coding for real-time device-to-device communications[J].Eurasip Journal on Advances in Signal Processing,2016,2016(1):1-14.
[9]ABOUTORAB N,SADEGHI P.Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[J].IEEE Transactions on Vehicular Technology,2016,65(3):1212-1228.
[10]YAN Y,ZHANG B,LI C.Opportunistic network coding based cooperative retransmissions in D2D communications[J].Computer Networks,2017,113:72-83.
[11]BARYOSSEF Z,BIRK Y,JAYRAM T S,et al.Index coding with side information[J].IEEE Transactions on Information Theory,2011,57(3):1479-1494.
[2]GAO C,LI Y,ZHAO Y,et al.A two-level game theory approach for joint relay selection and resource allocation in network coding assisted D2D communications[J].IEEE Transactions on Mobile Computing,2017,16(10):2697-2711.
[3]DOUIK A,SOROUR S,AL-NAFFOURI T,et al.Instantly decodable network coding:from centralized to device-to-device communications[J].IEEE Communications Surveys&Tutorials,2017,19(2):1201-1224.
[4]AHLSWEDE R,CAI N,LI S Y R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
[5]CHATZIGEORGIOU I,TASSI A.Decoding delay performance of random linear network coding for broadcast[J].IEEE Transactions on Vehicular Technology,2017,66(8):7050-7060.
[6]牛腾,张冬梅,许魁,等.最小化重传次数的无线网络编码广播重传算法[J].信号处理,2017(10):1368-1376.
[7]ABOUTORAB N,SADEGHI P,TAJBAKHSH S E.Instantly decodable network coding for delay reduction in cooperative data exchange systems[C].IEEE International Symposium on Information Theory Proceedings.IEEE,2013:3095-3099.
[8]DOUIK A,SOROUR S,AL-NAFFOURI T Y,et al.Instantly decodable network coding for real-time device-to-device communications[J].Eurasip Journal on Advances in Signal Processing,2016,2016(1):1-14.
[9]ABOUTORAB N,SADEGHI P.Instantly decodable network coding for completion time or decoding delay reduction in cooperative data exchange systems[J].IEEE Transactions on Vehicular Technology,2016,65(3):1212-1228.
[10]YAN Y,ZHANG B,LI C.Opportunistic network coding based cooperative retransmissions in D2D communications[J].Computer Networks,2017,113:72-83.
[11]BARYOSSEF Z,BIRK Y,JAYRAM T S,et al.Index coding with side information[J].IEEE Transactions on Information Theory,2011,57(3):1479-1494.