Paper Info
Title
On optimal diversity in network-coding-based routing in wireless networks
Abstract
Network coding (NC) based opportunistic routing has been well studied, but the impact of routing diversity on the performance of NC-based routing remains largely unexplored. Towards understanding the importance of routing diversity in NC-based routing, we study the problems of estimating and minimizing the data delivery cost in NC-based routing. In particular, we propose an analytical framework for estimating the total number of packet transmissions for NC-based routing in arbitrary topologies. We design a greedy algorithm that minimizes the total transmission cost of NC-based routing and determines the corresponding forwarder set for each node. We prove the optimality of this algorithm and show that 1) nodes on the shortest path may not always be favored when selecting forwarders for NC-based routing and 2)the minimal cost of NC-based routing is upper-bounded by the cost of shortest path routing. Based on the greedy, optimal algorithm, we design and implement ONCR, a distributed minimal cost NC-based routing protocol. Using the NetEye sensor testbed, we comparatively study the performance of ONCR and existing approaches such as the single path routing protocol CTP and the NC-based opportunistic routing protocols MORE and CodeOR. Results show that ONCR achieves close to 100% delivery reliability while having the lowest delivery cost among all the protocols and 25-28% less than the second best protocol CTP. This low delivery cost also enables ONCR to achieve the highest network goodput, i.e., about two-fold improvement over MORE and CodeOR. Our findings demonstrate the significance of optimizing data forwarding diversity in NC-based routing for data delivery reliability, efficiency, and goodput.
Year
DOI
Venue
2015
10.1109/INFOCOM.2015.7218446
2015 IEEE Conference on Computer Communications (INFOCOM)
Keywords
Field
DocType
optimal diversity,network-coding-based routing,wireless networks,packet transmissions,greedy algorithm,shortest path routing,single path routing protocol,opportunistic routing protocols,ONCR,CTP
Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Enhanced Interior Gateway Routing Protocol,Policy-based routing,Computer network,Wireless Routing Protocol,Distributed computing,Zone Routing Protocol
Conference
ISSN
Citations 
PageRank 
0743-166X
3
0.39
References 
Authors
21
6
Name
Order
Citations
PageRank
Qiao Xiang130.39
Hongwei Zhang293567.71
Jianping Wang31422103.90
Guoliang Xing43416209.19
Shan Lin515722.13
Xue Liu63058193.41