California Partners for Advanced Transportation Technology

We consider a class of sensor networks with two special characteristics. First, the nodes periodically generate data for transfer to a distinguished node called the access point. Second, the nodes are (transmit) power and energy limited, but the access point, which communicates with the 'outside world', is not so limited. Such networks might be used for instance when a geographically distributed physical process, such as traffic on a freeway or at an urban street intersection, is periodically sensed for purposes of process control. We propose a medium access control scheme, called PEDAMACS, for this special class of networks. PEDAMACS uses the high-powered access point to synchronize the nodes and to schedule their transmissions and receptions in a TDMA manner. The protocol first enables the access point to gather topology (connectivity) information. A scheduling algorithm then determines when each node should transmit its data, and the access point announces the transmission schedule to the other nodes. The scheduling algorithm ideally should minimize the delay-the time needed for data from all nodes to reach the access point. However, this optimization problem is NP-complete. PEDAMACS instead uses a polynomial-time scheduling algorithm which guarantees a delay proportional to the number of nodes in the sensor network. Because PEDAMACS schedules node transmissions, its performance is much better than that of protocols designed for more general contention (or random access) networks in terms of power consumption, delay, fairness, and congestion control. The comparison is based on simulations in TOSSIM, a simulation environment for TinyOS, the operating system for the Berkeley sensor nodes. For the traffic application we consider, the PEDAMACS network provides a lifetime of several years compared to several months and days based on random access schemes with and without sleep cycles respectively, making sensor network technology economically viable.