Coding based wireless broadcast scheduling in real time applications

详细信息    查看全文

• 作者：Cheng Zhan ; ^{zhanc@swu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Fuyuan Xiao ^{xiaofuyuan@swu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Network coding ; Broadcast scheduling ; Real time ; Weighted graph
• 刊名：Journal of Network and Computer Applications
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：64
• 期：Complete
• 页码：194-203
• 全文大小：732 K

文摘

Using network coding in wireless networks can increase throughput and reduce energy consumption. However there are only a few works considering the quality of service which is important to real time applications. This paper focuses on network coding based broadcast scheduling problem in real time wireless networks with packet delay constraint and aims at minimizing the number of packets which miss their deadlines under two receiver models. In the first model, receiver drops the encoded packet which cannot be decoded immediately. We formulate the broadcast scheduling problem with an integer linear programming and prove that it is NP-hard. We also propose a packet encoding and broadcasting algorithm based on the maximum weight clique in the graph. In the second model, receiver can buffer all received encoded packets and decode out their wanted packets when enough packets are received. According to marking colors on the vertices of the weighted graph, an effective heuristic algorithm is proposed in this paper. Simulation results show that our algorithm significantly reduces the deadline miss ratio in most cases, which is an important performance metric in real time applications.