Energy saving and high delivery reliability are two essential metrics in wireless ad hoc networks. In this paper, we propose a joint power control and network coding (PCNC) scheme which regulates the transmission power to reduce the overall energy usage and uses network coding to improve reliability by reducing the number of packet retransmissions. To argue for PCNC scheme, we investigate both unicast and multicast routing scenarios. To evaluate routing optimality, we adopt expected utility as a metric, which integrates energy cost, reliability, and benefit value. Based on the expected utility, we explore the optimality in both unicast and multicast routing. For unicast routing, we propose an optimal algorithm. We show the NP-hardness of multicast routing problem, and also design a heuristic solution. Results from simulations demonstrate that PCNC improves the performance in terms of expected utility compared with existing techniques. 1. Introduction Wireless ad hoc networks drew lots of attention in recent years because of its potential applications in various areas. However, ad hoc networks suffer the energy shortage due to the limited power supply devices [1, 2] and unreliable communication caused by the unstable wireless medium [3, 4]. Therefore, saving energy and improving message delivery reliability are two important issues in the design of wireless ad hoc protocols. Wireless communications (e.g., sending a message) are usually the most energy-consuming events in wireless networks. Thus, one of the most straight approaches to reduce energy consumption is decreasing the transmission power at the senders. However, decreasing the transmission power will reduce the reliability of the link, which may incur packet loss during data propagation [5]. Packet loss leads to packet retransmissions, which consumes more energy. To balance energy cost and reliability, several approaches have been proposed, especially, transmission power control (TPC) and network coding (NC). TPC, which has been studied in [5, 6], focuses on adjusting transmission power level on each sender to reduce the energy consumption. In [5], TPC is applied to study the tradeoff between end-to-end reliability and energy consumption based on the probability link model. Different from [5], Li et al. [6] integrated TPC with retransmission to address the problem of energy-efficient reliable routing for wireless ad hoc networks. With TPC, the transmission power can be decreased at each node for the packet retransmissions. Their experimental results also demonstrate the benefits of adopting TPC
References
[1]
J. H. Chang and L. Tassiulas, “Energy conserving routing in wireless ad-hoc networks,” in Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '00), pp. 22–31, Tel Aviv, Israel, March 2000.
[2]
Q. Li, J. Aslam, and D. Rus, “Online power-aware routing in wireless adhoc networks,” in Proceedings of the Annual ACM International Conference on Mobile Computing and Networking (ACM MOBICOM '01), pp. 97–107, Rome, Italy, July 2001.
[3]
A. Cerpa, M. Potkonjak, J. L. Wong, and D. Estrin, “Temporal properties of low power wireless links: modeling and implications on multi-hop routing,” in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '05), pp. 414–425, May 2005.
[4]
D. Couto, D. Aguayo, B. Chambers, and R. Morris, “Performance of multihop wireless networks : shortest path is not enough,” SIGCOMM Computer Communication Review, vol. 33, no. 1, pp. 83–88, 2003.
[5]
A. Khandani, E. Modiano, J. Abounadi, and L. Zheng, “Reliability and route diversity in wireless networks,” in Proceedings of the Conference on Information Sciences and Systems (CISS '05), Baltimore, Md, USA, March 2005.
[6]
X.-Y. Li, Y. Wang, H. Chen, X. Chu, Y. Wu, and Y. Qi, “Reliable and energy-efficient routing for static wireless Ad Hoc networks with unreliable links,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 10, pp. 1408–1421, October 2009.
[7]
M. Ghaderi, D. Towsley, and J. Kurose, “Reliability gain of network coding in lossy wireless networks,” in Proceedings of the The 27th Conference on Computer Communications (IEEE INFOCOM '08), pp. 2171–2179, April 2008.
[8]
M. M Lu and J. Wu, “Erasure-coding based utility routing in multihop wireless network,” in Proceedings of the 6th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (IEEE MASS '09), pp. 168–177, Macau, China, October 2009.
[9]
J. Wu, M. Lu, and F. Li, “Utility-based opportunistic routing in multi-hop wireless networks,” in Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS '08), pp. 470–477, June 2008.
[10]
M. Lu and J. Wu, “Social welfare based routing in Ad Hoc networks,” in Proceedings of the 2006 International Conference on Parallel Processing (ICPP '06), pp. 211–218, August 2006.
[11]
M. Lu and J. Wu, “Utility-based data-gathering in wireless sensor networks with unstable links,” Lecture Notes in Computer Science, vol. 49, no. 4, pp. 13–24, 2008.
[12]
L. H. A. Correia, D. F. Macedo, A. L. dos Santos, A. A. F. Loureiro, and S. M. S. Nogueira, “Transmission power control techniques for wireless sensor networks,” Elsevier Computer Networks, vol. 51, no. 17, pp. 4765–4779, 2007.
[13]
P. Bergamo, A. Giovanardi, A. Travasoni, D. Maniezzo, G. Mazzini, and M. Zorzi, “Distributed power control for energy efficient routing in AD Hoc networks,” Wireless Networks, vol. 10, no. 1, pp. 29–42, 2004.
[14]
R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, 2000.
[15]
J. Jin, T. Ho, and H. Viswanathan, “Comparison of network coding and non-network coding schemes for multi-hop wireless networks,” in Proceedings of the IEEE International Symposium on Information Theory, pp. 197–201, July 2006.
[16]
M. Ghaderi, D. Towsley, and J. Kurose, “Reliability benefit of network coding,” Tech. Rep., Computer Science Department, University of Massachusetts Amherst, Amherst, Mass, USA, 2007.
[17]
M. Kurth, A. Zubow, and J. P. Redlich, “Cooperative opportunistic routing using transmit diversity in wireless mesh networks,” in Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08), pp. 1310–1318, Phoenix, Ariz, USA, April 2008.
[18]
K. Zeng, W. Lou, and H. Zhai, “On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks,” in Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (IEEE INFOCOM '08), pp. 816–824, April 2008.
[19]
D. S. Lun, M. Médard, and R. Koetter, “Network coding for efficient wireless unicast,” in Proceedings of the IEEE International Zurich Seminar on Digital Communications, pp. 74–77, February 2006.
[20]
C. Zhan, Y. Xu, J. Wang, and V. Lee, “Reliable multicast in wireless networks using network coding,” in Proceedings of the 6th IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS '09), pp. 506–515, Macau, China, October 2009.
[21]
T. Ho, M. Médard, R. Koetter et al., “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006.
[22]
A. E. Khandani, J. Abounadi, E. Modiano, and L. Zheng, “Reliability and route diversity in wireless networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 12, Article ID 4712690, pp. 4772–4776, 2008.
[23]
L. A. Petingi, “Reliability study of mesh networks modeled as random graphs,” in Proceedings of the International Conference on Mathematical Models for Engineering Science (MMES '10), pp. 85–93, November 2010.
[24]
J.-Q. Jin, T. Ho, and H. Viswanathan, “Comparison of network coding and non-network coding schemes for multihop wireless networks,” in Proceedings of the IEEE International Symposium on Information Theory, pp. 197–201, July 2006.
[25]
M. Cagalj, J.-P. Hubaux, and C. Enz, “Minimumenergy broadcast in all-wireless networks: NP-completeness and distribution issues,” in Proceedings of the Annual ACM International Conference on Mobile Computing and Networking (ACM MOBICOM '02), pp. 172–182, Atlanta, Ga, USA, 2002.
