
Research
Abstracts  2006 
Exploiting Concurrent Transmissions in Wireless Sensor NetworksKyle Jamieson & Hari BalakrishnanIntroductionRadio 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 energyefficient 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 FormulationConsider two transmissions, t_{1} and t_{2}. 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 bitmeters 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 nonoverlapping 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_{simultaneous}will 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 righthand sides of Equations 1 and 2 equal, we get that r = 1/2. This means that the breakeven point between concurrent and disjoint transmissions for capacity occurs when concurrent transmissions degrade the links by half. Above this breakeven point, it is worthwhile to transmit simultaneously, from a capacity standpoint. Now let us consider a capacityenergy 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 timeenergy. Supposing the two nodes in our example transmit separately, capacityenergy is: Equation 3: capacityenergy metric of nonoverlapping transmissions. And using the same reasoning as above, the capacityenergy of concurrent transmissions is: Equation 4: capacityenergy metric of overlapping transmissions. Combining Equations 3 and 4 yields a breakeven 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 ProposalIn 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 lowestloss neighbors are communicating, sigma is at most unity (otherwise there is some communicating pair with more loss than some interfering pair, which means that lowestloss 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 workSon et al. study the effects of concurrent radio transmissions in smallscale (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 widescale 802.11 networks, respectively. They both note a large "grey area" where packet reception rate is uncorrelated with signaltonoise 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. AcknowledgementsThis project is funded by the National Science Foundation under award number CNS0205445 and under a DARPA subcontract from BBN under the ACERT program. References:[1] Dongjin Son, Bhaskar Krishnamachari, and John Heidemann. Experimental Analysis of Concurrent Packet Transmissions in LowPower Wireless Networks. USCISI Technical Report ISITR2005609, November 2005. [2] Daniel Aguayo, John Bicket, Sanjit Biswas, Glen Judd, and Robert Morris. Linklevel Measurements From an 802.11b Mesh Network. In Proceedings of the ACM SIGCOMM Conference, pp. 121132, 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. 113, 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. 134147, Baltimore, MD, November 2004. [6] Kyle Jamieson, Bret Hull, Allen Miu, and Hari Balakrishnan. Understanding the RealWorld Performance of Carrier Sense. In Proceedings of the ACM SIGCOMM EWIND Workshop, pp. 5257, 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. MACAP: A MAC for Concurrent Transmissions in Multihop Wireless Networks. In Proceedings of the IEEE PerCom Conference, Dallas, TX, March 2003. 

