Mobile, Embedded, & Wireless Security

EE 565 - Computer Communication Networks - Winter 2008



Project Option II: Minimum Energy Broadcast in Wireless Networks



In this project, we will investigate the problem of energy-efficient broadcast routing in wireless networks. It is a challenging environment because every node operates with limited resources and multihop routing paths are used. The network lifetime is defined as the duration of time until the first node failure due to battery energy exhaustion. In case all the nodes have identical initial energy level, the node that spends the battery power at the highest rate will exhaust its battery first. If we want to extend the lifetime of the network, it is critical to incorporate the residual battery energy into route selection criteria. The purpose of this project is to implement, compare, and improve upon several routing protocols for broadcast routing. As background reading, please read the following papers:
  1. J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks, Proc. IEEE INFOCOM 2000.
  2. M. Cagalj, J.-P. Hubaux, and C. Enz, Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues, MOBICOM'02, September, 2002, Atlanta, Georgia, USA.
  3. I. Kang and R. Poovendran, Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks, ICC 2003.
  4. I. Maric and R. D. Yates, Maximum Lifetime of Cooperative Broadcast in Wireless Networks....

For each part of the project, you will be responsible for writing the necessary simulation code (reusing code from previous projects is recommended) and answer the questions asked of you. You may use any reasonable programming language. Prepare a detailed project write-up (ideally 8-12 pages, 15 pages max) containing the following: Create a .zip, .rar, or .tar archive including (1) your project write-up, (2) your source code, (3) a text file with instructions to run your code, and (4) a summary of project contributions by each group member. Submit this archive according to the online submission instructions.

Suppose that 15 nodes with ID i=1,...,15 are arranged in a 1 km2 area. The locations (xi,yi) and initial battery energy Ei(0) are given in the following table.
xiyiEi(0)
354.8362900534410250.25708447747405251704.59447224
438.432120155571013.30222728831756692879.52888797
550.0110164077460887.84916494569801287551.59784981
107.5495943295510 659.00445841065904902370.30008543
313.3668135835570 74.85300698775882248586.67950461
783.3575769932690 38.05347407879844569994.09625906
663.8796904087930401.93693809783701374686.88295816
909.5058920451220 532.20492125160602142446.24328069
227.2589367950470 704.01673804037005344439.53623574
76.7954636944207 276.69693360718603305735.08480975
566.6904236004090 187.27638956876107996570.38278599
182.7267344665840 626.72351707660107972141.72899902
531.4362326765130 600.32654250468103732224.28844496
826.2190881929880 833.79773528240707437897.77291161
788.3175434671790 537.07606689225406578464.01114772


Assume that there is no limit on the maximum transmission power Pmax and the path loss factor α = 2 in this project. Using these assumptions, construct a broadcast routing tree rooted at the source node 1. You are responsible for the following: