Research Abstracts - 2006

Exploiting Concurrent Transmissions in Wireless Sensor Networks

Kyle Jamieson & Hari Balakrishnan

Introduction

Radio transmissions in many wireless sensor networks take place in a shared radio communication medium which spans both space and time. While this feature of radio makes communication in a sensor network easy to organize, it introduces problems that must be overcome if the application requires energy-efficient communication.

The primary problem of radio is data loss due to packet collision when two or more radios are transmitting at the same time. When the network loses data, it must be retransmitted if the application requires a certain level of data fidelity, and doing so wastes energy and shortens the lifetime of the network. In this work we study how to jointly optimize power and capacity in a wireless sensor network.

Problem Formulation

Consider two transmissions, t₁ and t₂. We first examine the choice of wheather to allow the two transmissions to occur simultaneously. Suppose we are trying to maximize network capacity [3], that is bits per unit time, or bit-meters per unit time. Then since two transmissions are occuring, and each takes time proportional to 1/p where p is the probability of each transmission succeeding (assuming that they are equal), network capacity C_separate will be proportional to

Equation 1: capacity of non-overlapping transmissions.

Now suppose we allow the two transmissions to occur simultaneously. Then the probability of each transmission succeeding will be lowered to some value p', but since the transmissions occur concurrently in time, the network capacity acheived C_simultaneouswill be proportional to

Equation 2: capacity of overlapping transmissions.

Now let us consider the ratio r = p'/p. The ratio r is a measure of how much both links are degraded by concurrent transmissions. Setting the right-hand sides of Equations 1 and 2 equal, we get that r = 1/2. This means that the break-even point between concurrent and disjoint transmissions for capacity occurs when concurrent transmissions degrade the links by half. Above this break-even point, it is worthwhile to transmit simultaneously, from a capacity standpoint.

Now let us consider a capacity-energy standpoint. This is of interest to sensor network designers because sensor networks have limited amounts of battery energy available. Therefore, we will try to optimize bits per unit time-energy. Supposing the two nodes in our example transmit separately, capacity-energy is:

Equation 3: capacity-energy metric of non-overlapping transmissions.

And using the same reasoning as above, the capacity-energy of concurrent transmissions is:

Equation 4: capacity-energy metric of overlapping transmissions.

Combining Equations 3 and 4 yields a break-even point of r=1/sqrt(2) or 0.707. This means that from an energy standpoint, concurrent transmisions must not degrade links by more than thirty percent in order to be useful.

Our Proposal

In our proposed protocol, each node in the network maintains a table comprised of (src, dest, loss) triplets representing the signal attenuation between nearby pairs of nodes when src is the transmitter and dest is the receiver. This is called the loss table.

Every node also maintains a power table comprised of (src, noise, drop) triplets representing the ambient noise at a neighboring node and whether the last packet sent was dropped.

When a node hears the beginning of a packet on the shared communication medium, it consults the packet header and its table to determine if a concurrent transmission is possible. If it is, it switches from receive mode to transmit mode and sends the packet, all concurrent with the ongoing transmission.

Otherwise, carrier sense is turned on. Note that this means that if a node can't decode a transmitter's preamble, it can't perform the above algorithm and get an opportunity to transmit concurrently.

We define the interference ratio as follows:

Equation 4: interference ratio definition.

In general, the interference ratio is the ratio between the maximum pathloss between communicating neighbors and the minimum pathloss between the pairwise communicating neighbors. When the interference ratio is zero, there is no interference between concurrent transmissions. When the interference ratio is unity, there is maximum interference between concurrent transmissions. The interference ratio thus guides protocol designers in scheduling concurrent transmissions.

Also note that if lowest-loss neighbors are communicating, sigma is at most unity (otherwise there is some communicating pair with more loss than some interfering pair, which means that lowest-loss neighbors aren't communicating).

Note that from the standpoint of interference ratio, exposed terminals and hidden terminals can look identical. The difference is in carrier sense.

Related work

Son et al. study the effects of concurrent radio transmissions in small-scale (up to 12 nodes) narrowband FM sensor networks [1]. They use the Mica2 platform to show the effects that interfering transmissions have on packet error rate and SINR of radio transmissions.

Zhao and Govindan [4] and Aguayo et al. [2] study links in sensor networks and wide-scale 802.11 networks, respectively. They both note a large "grey area" where packet reception rate is uncorrelated with signal-to-noise ratio measurements.

Acharya et al. propose the idea of allowing concurrent transmissions in wireless local area networks [8], but do not use path loss information to determine when concurrent transmissions can take place.

Acknowledgements

This project is funded by the National Science Foundation under award number CNS-0205445 and under a DARPA sub-contract from BBN under the ACERT program.

References:

[1] Dongjin Son, Bhaskar Krishnamachari, and John Heidemann. Experimental Analysis of Concurrent Packet Transmissions in Low-Power Wireless Networks. USC-ISI Technical Report ISI-TR-2005-609, November 2005.

[2] Daniel Aguayo, John Bicket, Sanjit Biswas, Glen Judd, and Robert Morris. Link-level Measurements From an 802.11b Mesh Network. In Proceedings of the ACM SIGCOMM Conference, pp. 121--132, Portland, OR, August 2004.

[3] P. Gupta and P. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory 46 (2), March 2000.

[4] Jerry Zhao and Ramesh Govindan. Understanding Packet Delivery Performance in Dense Wireless Sensor Networks. In Proceedings of the ACM SenSys Conference, pp. 1--13, Los Angeles, CA, November 2003.

[5] Bret Hull, Kyle Jamieson, and Hari Balakrishnan. Mitigating Congestion in Wireless Sensor Networks. In Proceedings of the ACM SenSys Conference, pp. 134--147, Baltimore, MD, November 2004.

[6] Kyle Jamieson, Bret Hull, Allen Miu, and Hari Balakrishnan. Understanding the Real-World Performance of Carrier Sense. In Proceedings of the ACM SIGCOMM E-WIND Workshop, pp. 52--57, Philadelphia, PA, 2005.

[7] K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D. Culler. Exploiting the Capture Effect for Collision Detection and Recovery. In Proceedings of the IEEE EmNets Workshop, Sydney, Australia, May 2005.

[8] Arup Acharya, Archan Misra, Sorav Bansal. MACA-P: A MAC for Concurrent Transmissions in Multi-hop Wireless Networks. In Proceedings of the IEEE PerCom Conference, Dallas, TX, March 2003.