A Distributed TDMA Scheduling Algorithm for

3836 IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, VOL. 60, NO. 9, SEPTEMBER 2013 A Distributed TDMA Scheduling Algorithm for Target Tracking in Ultrasonic Sensor Networks Peng Cheng, Member, IEEE, Fan Zhang, Jiming Chen, Senior Member, IEEE, Youxian Sun, and Xuemin (Sherman) Shen, Fellow, IEEE Abstract—Ultrasonic sensors are able to provide highly ac- curate measurements if they are properly scheduled, otherwise, the intersensor interference (ISI) could greatly deteriorate the performance. In addition, the scheduling scheme should be per- formed in a distributed and energy-efficient way so that it can be conveniently implemented for a large-scale network. In this paper, for target tracking with multiple ultrasonic sensors, we convert the ISI avoidance problem to the problem of multiple access in a shared channel and adopt the time division multi- ple access strategy which has the properties of being collision free and energy efficient. Then, by graph theory, the scheduling problem is transformed into a coloring problem which aims at minimizing the number of used colors. Since the original problem has been proved to be NP-hard, we propose a distributed- saturation-degree-based algorithm (DSDA) which can be imple- mented locally by each node with information collected from its neighbors. Furthermore, we verify that an interference-free schedule is guaranteed to be obtained by DSDA. We derive ana- lytical results for the complexity of this algorithm. Specifically, for different sensor network topologies, we prove that the expected converging time and the expected message transmissions per node are both upper bounded byO(δ), where δ is the maximum neigh- borhood size in the network. Extensive simulations demonstrate the effectiveness of our algorithm. Index Terms—Coloring problem, distributed time division mul- tiple access (TDMA) scheduling, intersensor interference (ISI) avoidance, target tracking. I. INTRODUCTION W IRELESS SENSOR networks (WSNs) have been con-sidered as a promising technique for different ap- plications [1]–[3], where target localization/tracking is a fundamental requirement for the technique. Several approaches have been proposed for target tracking within WSNs [4]–[7]. According to the target behavior, most of the previous works Manuscript received February 20, 2012; revised May 3, 2012; accepted June 20, 2012. Date of publication August 13, 2012; date of current ver- sion May 2, 2013. This work was supported in part by the Natural Science Foundation of China under Grant 61061130563, Grant 61004060, and Grant 60974122; by the National High-Technology Research and Development Pro- gram of China under Grant 2011AA04010; by the Specialized Research Fund for the Doctoral Program of China under Grant 20100101110066; and by the Natural Science Foundation of Zhejiang Province under Grant R1100324. Corresponding author: J. Chen. P. Cheng, F. Zhang, J. Chen, and Y. Sun are with the State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China (e-mail: pcheng@iipc.zju.edu.cn; zhangfan@iipc.zju.edu.cn; jmchen@ ieee.org; yxsun@iipc.zju.edu.cn). X. Shen is with the Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON N2L 3G1, Canada (e-mail: xshen@ bbcr.uwaterloo.ca). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIE.2012.2208439 can be categorized into two classes, cooperative [4], [5] and noncooperative ones [6], [8]. A cooperative target, as part of the network, can emit certain forms of physical signals that reveal its presence or report its own identification. In the non- cooperative scenario, however, the target will not provide any information of its own existence to the network cooperatively. Therefore, the sensor nodes have to emit the signal actively so that the target can be detected by the feedback signal. For example, a tracking system for noncooperative targets is designed in [8] by utilizing the passive infrared sensors for target detection and active ultrasonic sensors for ranging. In noncooperative tracking systems where the echo-based sensors like ultrasonic sensors are used, the intersensor inter- ference (ISI) becomes severe particularly when nearby active sensors work simultaneously in the same frequency band. Such interference results in erroneous sensor readings which may cause an unacceptable tracking performance with a high prob- ability. Therefore, it is necessary to schedule the activation of sensors at each time step to ensure that, in any ISI region, the number of sensors that are detecting the target should never be more than one at any specific time. In fact, if we take the ranging operation of a sensor node as the occupation of a shared channel, the ISI problem among active ultrasonic sensors in WSNs can be converted to the problem of multiple access in a shared channel. Hence, we can deal with the ISI avoidance problem in a similar way as the media access control (MAC) problem. A common MAC paradigm is carrier sense multiple access (CSMA), which is a simple, flexible, and robust contention- based access protocol and particularly fits for the networks with dynamic topology. However, it still suffers from the ad- ditional collisions which introduce serious energy waste, high overhead, and throughput degradation on the already-resource- constrained sensor nodes [9], [10]. Note that the distributed interfering sensor scheduling (DSS) algorithm proposed in [11] is based on CSMA, which requires the sensor nodes to negotiate with each other frequently to decide the tasking node and results in high energy consumption. Another classic access scheme is time division multiple access (TDMA) which divides the time into different slots that are assigned to different neighboring sensor nodes for access in a stationary way. The TDMA scheme often utilizes the topology information as a basis for access scheduling, requires clock synchronization among neighbors, and thus may lack efficiency and scalability when the networks are subject to frequent topology changes. However, the TDMA scheme does not need frequent information exchange among sensors 0278-0046/$31.00 © 2012 IEEE CHENG et al.: DISTRIBUTED TDMA SCHEDULING ALGORITHM FOR TARGET TRACKING IN SENSOR NETWORKS 3837 as long as the topology does not change; thus, the additional energy consumption for ISI scheduling can be greatly reduced. Moreover, it is a totally collision-free protocol which helps to improve the channel utilization. Therefore, the TDMA scheme is highly preferred in the access scheduling design of many WSN applications [12]–[14], particularly when the topology of a network is stationary most of time, which is the main scenario considered in this paper. Consider that a number of sensor nodes with the same sensing range are deployed in a field of interest, where the target moves following an unknown trajectory. Since the sensor nodes have limited computational capacity and constrained resources, it is desirable to design a lightweight and distributed activation scheme to avoid the ISI among nearby sensor nodes while achieving good tracking accuracy. In this paper, with the TDMA scheme, we focus on designing a static duty- cycled activation policy by exploring the local information of topology.1 Taking the sensor nodes as vertices and the interfer- ence relations as edges (determined by the position and sensing range of sensor nodes), we transform the activation design issue into a coloring problem. The performance metric is to minimize the number of used colors, which corresponds to the number of time slots, so that the average sampling rate can be maxi- mized. Our contributions of this paper can be summarized as follows. 1) We consider the ISI avoidance problem for target tracking in ultrasonic sensor networks with stationary topology most of the time. The TDMA scheme is adopted, and the issue is transformed into a coloring problem by graph theory. 2) Since the coloring problem has been proved to be NP-hard, a distributed-saturation-degree-based schedul- ing algorithm is proposed to solve the problem, which can be implemented in a distributed and parallel way and, therefore, greatly increase the sampling rate to achieve a better tracking performance. 3) We verify that distributed-saturation-degree-based algo- rithm (DSDA) is guaranteed to generate an interference- free schedule. We provide an upper bound of the converging time for DSDA. For different sensor network topologies, we prove that the upper bound of the expected converging time can be greatly reduced to a linear func- tion of the maximum neighborhood size in the network. 4) We evaluate the performance of our algorithm by exten- sive simulations. The remainder of this paper is organized as follows: Some related works on sensor scheduling are introduced in Section II. Section III demonstrates that the TDMA scheme is suitable to solve the ISI avoidance problem and how the corresponding issue can be transformed into a coloring problem. Section IV presents the details of DSDA including the theoretical analysis for the performance of the algorithm. Section V evaluates the algorithm with extensive simulations. Finally, conclusions and future works are given in Section VI. 1The primary concept is presented in [15]. II. RELATED WORKS Sensor scheduling has been a hot research topic for the past two decades. Different formulations and approaches have been proposed. Some previous works have addressed the sensor scheduling problem for different tracking systems in WSNs, most of which mainly focus on the tradeoff between tracking performance and energy consumption. In [16], several feasible measures of information utility are introduced for considering the problem of distributed tracking with WSNs. In [17], the problem is formulated as a partially observable Markov decision process. A Monte Carlo method is developed, which combines the particle filters for belief- state estimation and a sampling-based Q-value approximation for lookahead. In [18], the problem of stochastically selecting sensors is investigated, which aims to minimize the expected tracking error covariance. Priority list sensor scheduling is proposed in [19], where the main idea is to prioritize the sensor nodes according to local sensor schedules based on the predicted estimation error. Adap- tive sensor activation is introduced in [20], which dynamically adjusts the activation range of sensor, and a closed-loop control algorithm is proposed according to the feedback of tracking quality. In [21], an adaptive multisensor scheduling scheme is proposed for collaborative target tracking in WSNs. The main idea is to calculate the sampling interval according to a specification of the tracking accuracy and then select the cluster of tasking sensors based on their joint detection probability. In [22], the weighted sum of error covariance and the sensor usage cost are used as the performance measure. The authors also propose several suboptimal sensor scheduling algorithms for single target tracking with different sensor battery energy cases. In [23], a scheduling scheme is proposed to improve the scalability and energy efficiency by limiting the number of active nodes participating in localization while maintaining sufficient coverage to ensure an acceptable location error. Note that the interference caused by ultrasonic sensing has not been taken into account in the aforementioned works, and the methods cannot be applied directly to deal with the ISI problem for active sensors. The work of [6] considers a similar ISI avoidance problem to ours. However, only two centralized sensor scheduling schemes are investigated, which cannot be easily applied to large-scale networks in a distributed way. III. PROBLEM FORMULATION We formalize the sensor scheduling problem for ISI avoid- ance in the context of target tracking. Suppose that a network of active ultrasonic sensor nodes has been deployed at a set of locations with the task of tracking the noncooperative target. In order to avoid the ISI, in any ISI region, only one sensor node is tasked to actuate its ultrasonic sensors for range measurement at each time, and the time difference between two successive measurement epoches should be larger than Td, where Td is the die-out time of the ultrasonic wave in a ranging operation. The activated node then sends its data to the base station where the extended Kalman filter (EKF) is applied to estimate the state of the target. 3838 IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, VOL. 60, NO. 9, SEPTEMBER 2013 TABLE I NOTATIONS In order to design a lightweight and distributed sensor scheduling scheme, we adopt the TDMA strategy due to its properties of being collision free and energy efficient. In the TDMA slot assignment, the real time is divided into nonover- lapping periodic cycles called time frames which can be further divided into nonoverlapping equal time slots. The time slots are assigned to nodes for data transmission. Similarly, by setting the time slot length as Td and letting each sensor node sense the target at its allocated time slot, a periodic interference-free sen- sor scheduling scheme can be obtained from such collision-free TDMA slot assignment. Therefore, the key problem becomes how to conduct an efficient TDMA slot assignment. Graph coloring problem has been regarded as a convenient tool for the channel assignment problem in the time, frequency, and code domains [24]. Given a simple graph, G = (V,E), where V is the set of vertices and E is the set of edges. For each vertex v, define its neighborhood N(v) = {u : {u, v} ∈ E} and vertex degree d(v) = |N(v)|. Then, the vertex coloring problem is to find a color assignment for the vertices of G : V (G) f−→ F , where f is the assignment function and F is a set of colors, usually represented by some small subset of positive integers, so that any two adjacent vertices will be given different colors. From the view of graph theory, we consider the nodes as vertices and the interference relations as edges. An edge will exist between nodes u and v if and only if the Euclidean distance between them does not exceed 2rd, where rd is the detection range of the ultrasonic sensor. After each node gets its color which represents a determined TDMA time slot within a time frame, it will activate itself to detect the target at such slot during each time frame for interference-free sensing. Table I gives a summary of notations used in this paper. It is shown in [8] that the tracking performance can benefit from a higher sampling frequency. Therefore, in order to im- prove the tracking performance, it is desirable to minimize the number of used colors so that the minimum time frame, i.e., the highest sampling rate, can be achieved. Thus, the problem considered in this paper is to find the optimal coloring solution for the following problem: min |F | s.t. f(u) �= f(v), if ‖xv − xu‖ ≤ 2rd where u, v ∈ V . However, according to [25] and [26], finding an optimal solution for this problem is NP-hard. Therefore, it is critical to propose a heuristic but effective algorithm which can provide a satisfactory performance. Moreover, it is highly preferred if the algorithm can be implemented in a distributed way. Considering time efficiency and energy cost, we will use three metrics to evaluate the heuristic algorithm: • number of used color: the number of colors required to properly color the entire graph by the given algorithm; • running time: the amount of time taken by the given algorithm to color all the nodes in the graph; • message complexity: the number of messages transmitted by all the nodes during the coloring process. IV. DSDA Motivated by a centralized heuristic coloring algorithm DSATUR in [27], we propose the DSDA which solves the ISI avoidance problem in a completely distributed manner. Note that the algorithm in [27] is a centralized algorithm which requires that each node must know the global information of the network. Before presenting the main algorithm, we would like to first introduce some useful definitions and preliminaries. Define the saturation degree of vertex v, denoted by sd(v), as the number of different colors assigned to the neighbors of v. In order to utilize saturation degree heuristic in a distributed way, we introduce saturation degree indicator (SDI) for each node to calculate the priorities of the nodes within its neighborhood for coloring locally SDIv(u) = (Δ(v) + 1) · sd(u) + d(u) + rand(u) where Δ(v) = max w∈N(v) ⋃ {v} d(w) u ∈ S(v) =UN(v) ⋃ {v} and UN(v) denotes the uncolored neighborhood of v and rand(u) ∈ (0, 1) is a random value generate by node u for tie breaking. Note that Δ(v) is a constant for node v if the graph structure does not change. Additionally, we have the following proposition and definition. Proposition 1: The SDI satisfies the following: 1) ∀ u,w ∈ S(v), SDIv(u) �= SDIv(w); 2) SDIv(v) > SDIv(w) ⇐⇒ SDIw(v) > SDIw(w). Definition 1: Node v is an Extremum Node if the following condition is satisfied: SDIv(v) = max u∈S(v) SDIv(u). CHENG et al.: DISTRIBUTED TDMA SCHEDULING ALGORITHM FOR TARGET TRACKING IN SENSOR NETWORKS 3839 A. Algorithm Specification 1) Assumptions: For simplifying the statements, several as- sumptions are adopted as follows. 1) Each node has a unique node identification, and all nodes in the network are synchronized. 2) At the initial state, each node knows the IDs and degrees of its neighbors; thus, Δ(v) is known for each node v. 3) The range of the radio signal is equal to the ISI range. 4) Each one-hop message can be successfully delivered. Note that the first assumption means that all the nodes within the network are distinguishable and own the same time clock which is the foundation of the TDMA mechanism. The second assumption means that the network has been initialized already, which is for simplifying the whole process so that we can focus on the coloring process. The third assumption is to ensure that the network topology is identical with the interference graph. The last assumption guarantees the qual- ity of communication which is practical and not difficult to implement. 2) DSDA: The idea is to let each node decide its own slot according to the information collected from its neighboring nodes. For clarification, we define two types of data which represent the neighborhood information of each node. Specifically, LC(v) represents the list of colored neighbors of node v, as well as their colors. LUC(v) contains the infor- mation of uncolored neighbors of v, including the saturation degrees, degrees, and random values. Thus, we can get sd(v) from LC(v) and SDIv(u) from LUC(v). In addition, there is a positive real value named age attached to each item in LUC, which represents the “vitality” of the item. DSDA runs in rounds, and each round is divided into two sequential subrounds: subrnd1 and subrnd2. The algorithm runs individually on each node regardless of the progress of the whole network, and during each round, the detailed procedure is summarized as follows. 1) During subrnd1, by using a constant maxAge which is set as an upper bound for the item age in LUC, each uncolored node u first updates the age of each item in LUC(u) and deletes the expired items which is caused by node death or topology change. After that, u calculates SDIu(v) for itself and its uncolored neighbors to find out whether it is an Extremum Node. If u is an Extremum Node which implies that it can be colored in this round, it picks its color to be the minimum of the colors that have not been taken by its neighbors before this round, and the information can be obtained from LC(u). Then, u enters the colored state and broadcasts a release message containing its selected color. 2) During subrnd2, on receivin