Abstract
Network wide broadcasting in Mobile Ad Hoc Networks(MANET) provides important control and route establish-ment functionality for a number of unicast and multicastprotocols. We present an overview of the recent progressof broadcasting and multicasting in wireless ad hoc net-works. We discuss two energy models that could be usedfor broadcast: one is non-adjustable power and one is ad-justable power. If the power consumed at each node isnot adjustable, minimizing the total power used by a re-liable broadcast tree is equivalent to the minimum con-nected dominating set problem (MCDS), i.e., minimize thenumber of nodes that relay the message, since all relayingnodes of a reliable broadcast form a connected dominat-ing set (CDS). If the power consumed at each node is ad-justable, we assume that the power consumed by a relaynode u is kuvk., where real number . 2 [2; 5] depends ontransmission environment and v is the farthest neighborof u in the broadcast tree. For both models, we reviewedseveral centralized methods that compute broadcast treesconsuming the energy within a constant factor of the op-timum if the original communication graph is unit diskgraph. Since centralized methods are expensive to imple-ment, We further reviewed several localized methods thatcan approximate the minimum energy broadcast tree fornon-adjustable power case. For adjustable power case, nolocalized methods can approximate the minimum energybroadcast tree and thus review several currently best pos-sible heuristics. Several local improvement methods andactivity scheduling of nodes (active, idle, sleep) are alsodiscussed.
Keywords: Wireless networks, network optimiza-tion, power consumption, broadcasting, multicasting.
1 Introduction
Wireless Ad Hoc Networks: Due to its poten-tial applications in various situations such as battle-field, emergency relief, environment monitoring, andso on, wireless ad hoc networks [1, 2, 3, 4] have re-cently emerged as a premier research topic. Wirelessnetworks consist of a set of wireless nodes which arespread over a geographical area. These nodes are ableto perform processing as well as capable of commu-nicating with each other by means of a wireless adhoc network. With coordination among these wire-less nodes, the network together will achieve a largertask both in urban environments and in inhospitableterrain. For example, the sheer numbers of wirelesssensors and the expected dynamics in these environ-ments present unique challenges in the design of wire-less sensor networks. Many excellent researches havebeen conducted to study problems in this new field[1, 2, 5, 3, 6, 4].In this chapter, we consider a wireless ad hoc net-work consisting of a set V of n wireless nodes dis-tributed in a two-dimensional plane. Each wirelessnode has an omni-directional antenna. This is attrac-tive because a single transmission of a node can bereceived by many nodes within its vicinity which, weassume, is a disk centered at the node. We call theradius of this disk the transmission range of this wire-less node. In other words, node v can receive the signalfrom node u if node v is within the transmission rangeof the sender u. Otherwise, two nodes communicatethrough multi-hop wireless links by using intermediatenodes to relay the message. Consequently, each nodein the wireless network also acts as a router, forward-ing data packets for other nodes. By a proper scaling,we assume that all nodes have the maximum trans-mission range equal to one unit. These wireless nodesdefine a unit disk graph UDG(V ) in which there is anedge between two nodes if and only if their Euclideandistance is at most one.


Download full report
http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf