Abstract
This chapter studies the joint link scheduling and topology control problems in wireless sensor networks. Given arbitrarily located sensor nodes on a plane, the task is to schedule all the wireless links (each representing a wireless transmission) between adjacent sensors using a minimum number of timeslots. There are two requirements for these problems: first, all the links must satisfy a certain property, such as that the wireless links form a data gathering tree towards the sink node; second, all the links simultaneously scheduled in the same timeslot must satisfy the SINR constraints. This chapter focuses on various scheduling algorithms for both arbitrarily constructed link topologies and the data gathering tree topology. We also discuss possible research directions.
TopIntroduction
Cross-layer design of wireless ad-hoc and sensor networks has received increasing attention in the past several years (Goldsmith & Wicker, 2002). Most of these work focused on the interplay among the physical, MAC and network layer, resulting in various joint designs of power control, modulation and coding, link scheduling and routing. Very few of them, however, have considered joint design with topology control. Topology control (Gao et al., 2008; Santi, 2005) is the strategy to tune the sensors’ transmitting powers so that the sensor nodes collectively can maintain a certain global topology such as connectivity. The goal in topology control is to minimize the sensors’ power consumption while trying to provide sufficient network capacity. Topology control plays a very important role in wireless sensor networks: first, the packets are sent via radio transmissions by which there must be a connected topology (or other topologies, such as t-spanner) to guarantee that the information collected at each sensor can be forwarded to the other sensors; second, since all the sensor nodes are power limited, energy efficiency is a fundamental challenge in sensor networks; third, a high throughput capacity can ensure the collected information to be more quickly sent to the sink nodes, which is crucial in many critical sensor applications. The higher throughput capacity achieved by topology control in wireless sensor networks can be realized by reducing the network’s interferences (Wattenhofer et al., 2001), the degree of which is generally considered to be directly related to the sensor network’s maximum node degree (Wang & Li, 2003). Such interference degree, as well as the other graph-based interference models developed later by many other researchers (Schmid & Wattenhofer, 2006), however, can not accurately reflect the actual capacity gains of wireless sensor networks in reality. For example, it has been shown that low node degree does not necessarily mean low interference degree (Burkhart et al., 2004), and a higher graph-based interference degree does not necessarily mean lower network capacity (Hua & Lau, 2008). In this chapter, we study two related joint link scheduling and topology control problems, the goal of which is to minimize the number of timeslots used to schedule all the wireless links (transmissions) in any given topology or a specifically constructed topology. Here the number of timeslots used corresponds to the reciprocal of the network capacity.
Key Terms in this Chapter
Linear Power Assignment: If each link in the concurrently scheduled links employs the transmission power which is proportional to the corresponding link’s length (the distance from the transmitter to the receiver) to the power of the path loss exponent, we call it a linear power assignment.
Nonlinear Power Assignment: We useto denote the length diversity of all the linksscheduled in the same timeslot. And we sort the links in a non-increasing order of their lengths. Then we assign thevalue (the power scaling exponent) to each link (), and the lower the length magnitude of the links, the higher the value. In particular, the links with the lowest length magnitude have the highestvalue of, and the links with the highest length magnitude have the lowestvalue of 1. Then if the link i uses the transmission power, we say it is a nonlinear power assignment. Here is a function of the parameters,,and the number of the links.
Length Diversity: A notion to describe the number of magnitudes of lengths in a set of links. In particular, the length diversity ofis: is the length of link i)
Constant (Uniform) Power Assignment: If all the concurrently scheduled links employ the same transmission power, we call it a constant (uniform) power assignment.
Topology Control: Adjustment of the links’ transmission powers so that these links fulfill a network-wide property, such as connectivity, low interference and capacity improvement.
Wireless Link: A wireless transmission comprised by a source node (transmitter) and a destination node (receiver).
SINR Model: A specific interference model which is dependent on the so called signal-to-interference-plus-noise-ratio (SINR). In this model, we say that a link i has been successfully scheduled if and only if the power received by the link’s receiverfrom its corresponding transmitteris at least a factorhigher than the sum of the received powers from the other concurrently scheduled links’ transmitters plus the background noise. Here the received power attenuates with distance, i.e., it equals to the transmitted power divided by the distance between the sender and receiver to the power of the path loss exponent.
Link Independent Set: A set of links which can be concurrently scheduled under the SINR model.
Pareto-Optimal Power Assignment: According to Property 4 of the link gain matrix H, if we set the transmission powers based on the power vector, we call it a Pareto-optimal power assignment.