Wireless Networks 12, 63–78, 2006C2006 Springer Science + Business Media, Inc. Manufactured in The Netherlands.Energy-Efficient, Collision-Free Medium Access Control for WirelessSensor Networks∗VENKATESH RAJENDRAN∗∗, KATIA OBRACZKA and J.J. GARCIA-LUNA-ACEVESDepartment of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, Santa Cruz, CA 95064Abstract. Thetraffic-adaptivemedium access protocol (TRAMA) is introduced for energy-efficientcollision-free channel access in wirelesssensor networks. TRAMA reduces energy consumption by ensuring that unicast and broadcast transmissions incur no collisions, and byallowing nodes to assume a low-power, idle state whenever they are not transmitting or receiving. TRAMA assumes that time is slotted anduses a distributed election scheme based on information about traffic at each node to determine which node can transmit at a particular timeslot. Using traffic information, TRAMA avoids assigning time slots to nodes with no traffic to send, and also allows nodes to determinewhen they can switch off to idle mode and not listen to the channel. TRAMA is shown to be fair and correct, in that no idle node is anintended receiver and no receiver suffers collisions. An analytical model to quantify the performance of TRAMA is presented and theresults are verified by simulation. The performance of TRAMA is evaluated through extensive simulations using both synthetic- as wellas sensor-network scenarios. The results indicate that TRAMA outperforms contention-based protocols (CSMA, 802.11 and S-MAC) andalso static scheduled-access protocols (NAMA) with significant energy savings.Keywords: sensor networks, energy-efficient scheduling, traffic-adaptive medium access, ad hoc networks1. IntroductionSensor networks typically refer to large ensembles of inter-connected nodes that, besides processing and communicationcapabilities, include one or more sensing devices (e.g., ther-mistors, magnetometers, light detectors). The deployment ofsuch networks is usually done in an ad-hoc manner (e.g.,dropping sensors from an aircraft on the field) which im-plies that sensor-network nodes need to self-organize into amulti-hop wireless ad-hoc network. Many large-scale sen-sor networks will consist of battery-powered sensor nodeswhose battery may be difficult to recharge, or that the nodesthemselves may be so cheap that recharging them may not becost-effective.As the hardware for sensor nodes has become increasinglymore affordable and widely available, sensor networks haveemerged as an ideal solution to a number of applications inboth civilian and military scenarios. Some example applica-tions include monitoring and surveillance of large, remote orinaccessible areas over extended periods of time. However,a major challenge facing the development and eventual de-ployment of large-scale sensor networks is the scheduling oftransmissions among nodes in a way that (i) automaticallyadapts to changes in traffic, node state, or connectivity; and(ii) prolongs the battery life of each node.∗This work was supported in part by the NSF-NGI grant number ANI-9813724 and by the Jack Baskin Chair of Computer Engineering at UCSC.∗∗Corresponding author.E-mail: [email protected]. BackgroundThere is an extensive body of work on medium access control(MAC) protocols for multihop wireless networks, dating backto DARPA’s packet radio program (e.g., [5, 6, 8, 14–16]).These MAC protocols can be categorized as contention- andschedule-based.The best-known example of contention-based MAC pro-tocol is the distributed coordination function (DCF) of theIEEE 802.11b standard [10]. 802.11’s DCF uses the carriersense multiple access (CSMA) technique combined with afour-way handshake that attempts to avoid collisions of datapackets. In terms of energy consumption, a key limitationof traditional contention-based schemes is that nodes con-sume energy needlessly when they are idle (i.e., not trans-mitting or receiving) as well as when collisions occur. Untilrecently, very little work has been reported on contention-based schemes that focus on energy efficiency.One notable exception is PAMAS [18], one of the earli-est contention-based proposals to address power efficiency inchannel access. PAMAS saves energy by attempting to avoidoverhearing among neighboring nodes. To achieve this, PA-MAS uses out-of-band signaling. Woo and Culler [22] ad-dress variations of CSMA tailored for sensor networks, andpropose an adaptive rate control mechanism to achieve fairbandwidth allocation among sensor network nodes. In thepower save (PS) mode in IEEE 802.11 DCF, nodes sleep pe-riodically. Tseng et al. [21] investigated three sleep modalitiesin 802.11 DCF for multi-hop networks. The sensor-MAC pro-tocol [23], or S-MAC, exhibits similar functionality to that of64 RAJENDRAN, OBRACZKA AND GARCIA-LUNA-ACEVESPAMAS and the protocol by Tseng et al. Like the other ap-proaches, S-MAC avoids overhearing and nodes periodicallysleep. However, unlike PAMAS, S-MAC uses in-line signal-ing, and unlike modalities of the PC mode in 802.11 DCF,neighboring nodes can synchronize their sleep schedules.The probability of collisions of control or data packetsin any contention-based scheme increases with the offeredload, resulting in degraded channel utilization and reducedbattery life. This motivates the need for establishing trans-mission schedules statically or dynamically to allow nodesto receive data packets without collisions. The transmissionschedule established in a wireless network can be topology-independent or dependent [2,4,12,17]. The scheduled-accessMAC protocol described by Sohrabi and Pottie [19] uses acombination of TDMA and FDMA or CDMA for accessingthe channel. The main drawback of this scheme is that, likemost fixed scheduling mechanisms, time slots are wasted if anode does not have any data to send to the intended receiver.The Node Activation Multiple Access (NAMA) [2] uses adistributed election algorithm to achieve collision-free trans-missions. For each time slot, NAMA selects only one trans-mitter per two-hop neighborhood and hence all nodes in theone-hop neighborhood of the transmitter are able to receivedata collision-free. However, NAMA does not address energyconservation. In fact, very few proposals, if any, implementenergy-aware medium access scheduling.1.2. FocusSection 2 introduces the TRaffic-Adaptive Medium Access(TRAMA) protocol, which