Efficient Broadcast in Wireless Ad Hoc and Sensor Networks with a Realistic Physical Layer

Efficient Broadcast in Wireless Ad Hoc and Sensor Networks with a Realistic Physical Layer Hui Xu and J.J. Garcia-Luna-Aceves Computer Engineering, University of California at Santa Cruz, CA, USA Email: { xuhui,jj } @soe.ucsc.edu Abstract— To minimize energy consumption efficient broadcast- ing in ad hoc and sensor networks aims to select small sets of forwarding nodes and to minimize the transmission radius. However, the physical-layer characteristics of radio links are such that chosen receivers which may not be able to decode packets sent to them, even without multiple access interference. We present an analytical model to show that the transmission radius used for nodes can be used to establish a tradeoff between minimizing energy consumption and ensuring network coverage. We then propose a mechanism called redundant radii, which involves using two transmission radii, to form a buffer zone that guarantees the availability of logical links in the physical network, one for broadcast-tree calculation and the other for actual data transmission. The effectiveness of the proposed scheme in improving network coverage is validated analytically and by simulation. I. I NTRODUCTION Broadcasting is an indispensable operation in wireless sensor and ad hoc networks. It is needed for route discovery, infor- mation dissemination, publication of services, data gathering, task distribution, time synchronization, and so on. Given that untethered devices rely on batteries with limited capacity, one of the most important criteria when designing commu- nication protocols is energy efficiency. Hence, a key objec- tive of broadcasting algorithms and protocols is to minimize energy consumption. Tree-based broadcasts provide the best energy efficiency, because they select the smallest number of forwarding nodes. Because energy consumption depends on transmission ranges, a straightforward way to preserve energy is to limit the transmission radii to those distances needed to reach selected neighboring nodes. However, while transmission radius adaptation has been explored in many broadcasting schemes in the past, they have assumed an ideal physical- layer model in which nodes within a given transmission range receive packets with probability 1. This, of course, is not realistic in most practical situations. In reality, the received power levels may show significant variations around the mean power and nodes can decode packets with probabilities smaller than 1. As a consequence, tree-based broadcasting schemes that minimize the number of forwarding nodes may suffer from poor network coverage. The work presented in this paper is inspired by recent research work in [1], [2], [3], [4]. Takai et al. [1] showed the importance of the physical layer, even though the protocols evaluated do not directly interact with the physical layer. Stojmenovic et al. [2], [3], [4] presented guidelines on how to design routing and broadcasting in ad hoc and sensor networks taking physical layer impact into consideration. They applied the log normal shadow fading model to represent a realistic physical layer and derive the approximation for probability p(d) of receiving a packet successfully as a function of distance d between two nodes. They proposed several localized routing schemes for the case when position of destination is known, optimizing expected hop count (for hop by hop acknowledge- ment), or maximizing the probability of delivery (when no acknowledgements are sent). They considered localized power aware routing schemes under realistic physical layer. Finally, they mentioned about the research for broadcasting in ad hoc and sensor network with realistic physical layer and proposed a concept of dominating sets to be used in broadcasting process. Section II presents some preliminaries and the system model we assue in our study, and Section III presents an analytical model showing that the delivery ratio can be increased by lengthening the transmission radii of forwarding nodes; how- ever, this is attained by also increasing energy consumption at each such node. Hence, a tradeoff exists between increasing network coverage and minimizing energy consumption. We show how approximate radii can be computed and propose a general formula to derive transmission radii according to the required network coverage. Section IV proposes our “redundant radius” mechanism for efficient broadcasting, which makes use of the approximate radii calculation. After neighborhood information is collected, a smaller neighborhood range is used to calculate a broadcast tree; and then a longer radii is used as the actual transmission radii, which is based on the approximate transmission radii to form a buffer zone that guarantees the availability of logical links in the network. Section V addresses the effectiveness of the proposed scheme in improving the network coverage using simulations. II. P RELIMINARIES AND S YSTEM M ODEL Because of multipath effects [5] caused by reflection, diffrac- tion and scattering, the signal level obtained at a receiver is actually a vector sum of all signals incident from any direction or angle of arrival. Some signals will aid the direct path, while other signals will subtract (or tend to vector cancel) from the direct signal path. Finally, the received power levels may show significant variations which cause success reception as statistic variable. The above RF multipath problems can be mitigated in a number of ways: radio system design, antenna system design, signal or waveform design, building or environment design. However, multipath problems cannot be avoided completely;