Network Security and Distributed systems
Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks
Abstract:
In the paper, we described a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we consider a hierarchical sensor network that is composed of
(a) A static backbone of sparsely placed high-capability sensors which will assume the role of a cluster head (CH) upon triggered by certain signal events;
(b) Moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a pre-determined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information.
The CH that is usually closest to the target is (implicitly) selected as the leader and the dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.
Introduction
With the advancement of technologies, sensor networks have opened new vistas for a wide range of application domains. These sensor networks usually comprise small, low power devices that integrate sensors and actuators with limited on-board processing and wireless communication capabilities. One of their most important applications is target tracking. The type of signals to be sensed are determined based on the types of objects to be tracked.
In spite of the different targets to be tracked and the various signals to be sensed, tracking applications share several common characteristics:
First, the tracking system should report the location of the target to subscribers (usually remote controllers) accurately and in a timely manner.
Second, because the data collected by sensors may be redundant, correlated, and/or inconsistent, it is desirable to have sensors collaborate on processing the data and transporting a concise digest to subscribers.
Clustering
To facilitate collaborative data processing in target tracking centric sensor networks, the cluster architecture is usually used in which sensors are organized into clusters, with each cluster consisting of a cluster head (CH) and several neighboring sensors (members).
In the conventional cluster architecture, clusters are formed statically at the time of network deployment. The attributes of each cluster, such as the size of a cluster, the area it covers, and the members it possesses, are static. In spite of its simplicity, the static cluster architecture suffers from several drawbacks. First, fixed membership is not robust from the perspective of fault tolerance. If a CH dies of power depletion, all the sensors in the cluster render useless. In the case that sensors die, a cluster may not have sufficient sensors to carry out its tracking tasks. Second, fixed membership prevents sensor nodes in different clusters from sharing information and collaborating on data processing.
Dynamic clustering architectures, offer several desirable features. Formation of a cluster is triggered by certain events (e.g., detection of an approaching target with acoustic sounds). Specifically, when a sensor with sufficient battery and computational power, detects with a high signal-to-noise ratio (SNR), certain signals of interest, it volunteers to act as a CH. No explicit leader (CH) election is required, and hence no excessive message exchanges are incurred. On the other hand, a judicious, decentralized approach has to be used to ensure that for most of the time only one CH is active in the vicinity of a target to be tracked. Sensors in the vicinity of the active CH are “invited” to become members of the cluster and will report their sensor data to the CH. In this manner, a cluster is only formed in the area of high event concentration. Sensors do not statically belong to a cluster, and may support different clusters at different times. Moreover, as only one cluster is active in the vicinity of a target, redundant data is suppressed.
Dynamic clustering algorithm for single target tracking:
In acoustic tracking, two most common methods for target localization are the time delay-based and energy-based approaches. While time delay-based approaches are susceptible to estimation errors in time synchronization, on-set detection and echo effect, energy-based approaches are more robust in these aspects. Sensors in the acoustic tracking systems perform two types of computation: (1) sensing the energy level of signals; (2) sound analysis, classification, and data fusion. The former is not computational intensive and can be handled by sensors with minimal computation power. The later, however, requires much higher computation power. To this end, we consider a hierarchical sensor network that is composed of (a) a static backbone of sparsely placed high-capability sensors which will assume the role of a CH upon triggered by certain events of interest; and (b) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active in an on-demand fashion, when the acoustic signal strength detected by the CH exceeds a pre-determined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. After receiving a sufficient number of replies from sensors, the CH applies a localization method to estimate the location of the target and send a report to the subscribers.
There are several issues that we have to address and devise solution approaches in order to realize the notion of dynamic clustering: (I1) how CHs cooperate with one another to ensure that for most of the time only one CH (preferably the CH that is closest to the target1) is active; (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with non-redundant information to determine the target location; and (I3) both packets with which sensors respond to their CHs and packets that CHs report to subscribers do not incur significant collision.
The reason why the CH closer to the target should be activated is because the quality of sensing data decreases with the distance from the target. To deal with these issues, with the use of Voronoi diagram, a probabilistic leader volunteering procedure and a sensor replying method will be done. With the use of Voronoi diagram, each CH (or sensor) can calculate and tabulate the probability that given a distance estimate between a target and itself, the CH (sensor) is closest to the target. This information is used to set up the timer used by a CH to announce its willingness to be active in the leader volunteering process. If no other CHs volunteer before the timer expires, the CH becomes active; otherwise, it suppresses its timer. Similarly, this probabilistic information is also used by a sensor to determine whether or not it should respond to a CH upon request to provide sensor information and the timer value with which it responds to such a request.
SYSTEM OVERVIEW
A. Energy-Based Localization
The fundamental principle applied in the energy-based approach is that the signal strength (i.e., energy) of a received signal decreases exponentially with the propagation distance.
r i =a║x-xi ║-a +wi ,1≤i≤N, (1)
Where r i is the received signal strength in the ith sensor, a belongs to R is the(unknown) strength of an acoustic signal from the target, x belongs to R2 is the target position yet to be determined, xi belongs to R is the known position of the ith sensor, a is the (known) attenuation coefficient, and wi is the white Gaussian noise with zero-mean and variance σ2.
Instead of solving for the unknowns in Eq. (1) based on energy readings from multiple sensors, we use simple Voronoi diagram-based approach. Conceptually, each pair of energy readings, (r i, r j) from two sensors i, j determines a half plane that contains the target, i.e., r i >r j if the target is closer to i sensor than to sensor j and hence lies in the half plane that contains sensor. With multiple pairs of energy readings, the target location can be confined to be the intersection area of all the half planes. It can be shown that for a set of n sensor readings, n-1 out of the total n(n-1)/2 half planes are independent. Therefore, in order to obtain a bounded intersection area, at least four sensor readings are required.
B. Overview of Dynamic Clustering Algorithm
Because of the limited mobility nature of sensors, the calibration process of sensor locations is executed only once when the
Network is deployed. In this calibration process, geographical information required to construct the Voronoi diagram is collected, and the Voronoi diagram constructed. Furthermore, both CHs and sensors construct several tables to facilitate determination of the back-off timer values (to be used when a CH intends to volunteer itself as a leader and when a sensor intends to respond to a CH).
A CH volunteers to become active when it detects that the strength of an acoustic signal it receives exceeds a predetermined threshold and the signal matches one of the signal patterns, which the system intends to track. As multiple CHs may detect the acoustic signal with a sufficiently high signal-to-noise ratio and volunteer themselves as active leaders, a two-phase volunteering procedure to determine in a decentralized manner the CH with the strongest signal strength.
The tasks of an active CH include the following four steps:
1) Broadcasting a packet that contains the energy and the extracted signature of the detected signal to sensors,
2) Receiving replies from sensors,
3) Estimating the location of the target based on replies,
4) Sending the result to subscriber(s).
The extracted signature can be either the raw data or the extracted feature of a signal.
Upon receipt a broadcast packet from a CH, a sensor matches the signature with its buffered data. In the case of a match, the sensor then determines, with the use of the Voronoi diagram based table, whether or not it may be (i) the sensor that is closest to the target or (ii) one of the neighbors of the sensor that is closest to the target. If any of the above two conditions holds, it replies, after a random delay, to the CH the strength of the signal it receives. The random delay is determined based on the strength of the signal the sensor receives so as to mitigate collision. Once the CH collects enough replies, it ignores all subsequent replies, generates the localization result and sends the result back to subscribers. Sensors that decided to reply but have not yet done so (as their timers have not expired) stop replying, if they overhear the packet that carries the localization result. The relationship between the radio transmission range and the acoustic signal detection range determines the size of a cluster.
Detailed description of dynamic clustering algorithm:
The dynamic clustering algorithm is composed of four component mechanisms: initial distance calibration and tabulation, CH volunteering, sensor replying, and reporting of tracking results.
A. Distance Calibration and Tabulation
Before the acoustic tracing system starts to function, each sensor has to know the positions of sensors in its tracking ranges. Under the assumption that the radio transmission range is larger than the acoustic detection range, a sensor can notify other sensors of its ID, device function (CH or sensor), and location information by broadcast. To reduce the possibility of collisions, a broadcast packet is delayed by a back-off value determined based on the sensor ID.
Construction of Voronoi diagrams at a CH: After receiving the location information from all the neighboring sensors, a CH constructs two Voronoi diagrams around itself, one for the set of neighboring sensors and the other for the set of neighboring CHs.
Voronoi diagram of CHi. If a target locates within the inner dotted circle, CHi is sure that the target is in its Voronoi cell. On the other hand, if a target resides outside the outer dashed circle, CHi is sure that the target is out of its Voronoi cell.
Construction of the response table based on Voronoi diagrams at a CH:
After the Voronoi diagrams are constructed, a CH proceeds to construct the response table to facilitate determination of back-off timer values (to be used when the CH intends to volunteer itself as a leader). The table is indexed by the estimated distance from the target to the CH, d and each table entry stores the conditional probability that with the distance d, a target indeed locates within this CH’s Voronoi cell.
The distance from the target to a CH, say CHi can be estimated as d=(r/a) -1/ a .
That is, the possible position at which the target may be located is a circle centered at CHi and with radius d. Next, we derive the conditional probability, pr (i/d), that the target locates within the Voronoi cell of CHi given the distance from the target to CHi, d. Let d i,min and d i,max denote, respectively, the distance from CHi to its nearest neighboring CH and that from CHi to the farthest Voronoi vertex of its Voronoi cell. We have to consider three cases
1) d <1/2.d i,min is the nearest CH to the target because the circle that is centered at CHi and has a radius of d lies completely within CHi’s Voronoi cell. Hence pr (i/d) =1.0
2) d> d i,max :By the definition of d i,max the circle centered at CHi with a radius of d lies completely CHi’s Voronoi cell. Hence pr (i/d) =0.0.
3)1/2. d i,min < i,max, <> The circle is centered at CHi I and has a radius of d is partially located within CHi’s Voronoi cell and hence 0.0.≤ pr (i/d)≤ 1.0.
To keep the table size at a fixed value, we quantize the distance from the target to itself d as follows. The table contains k entries. The first entry is indexed by the maximum value of d (denoted as dmin) such that Pr (i/dmin) =1.0, while the last entry by the minimum value of d (denoted as dmax) such that Pr (i/dmax) =1.0. The other k-2 entries are indexed by values evenly spaced between dmin and dmax . Given an arbitrary distance d, a binary search is made to locate the two entries with the closest distance and interpolation is used to obtain the approximate value of pr (i/d).
B. Cluster Head Volunteering
In the first step of dynamic clustering, a CH volunteers to recruit sensors to form a cluster if its detected signal strength exceeds a predefined threshold. One fundamental design issue to consider is which CH(s) should be elected to form a cluster if more than one CH detects simultaneously signals with the strength exceeding the threshold. Note that if two or more clusters are active simultaneously, packets exchanged in one cluster may interfere/collide with those in the other cluster(s). Ideally, the CH that is closest to the target (or the CH with the largest SNR ratio) should be elected.
Determination of back-off timer values:
Without a centralized facility and/or excessive message exchanges for CH election, the most effective method to determine the active CH is to figure in the received signal strength into the determination of the back-off timer values used to send solicitation packets. A CH whose received signal strength exceeds the pre-determined threshold sets a back-off timer and does not broadcast its solicitation packet until the timer expires. If by the time the back-off timer expires, the CH receives a solicitation packet from some other CH, it cancels the timer. Specifically, the back-off time, D, for which CHi (with the estimated distance d) delays before sending its solicitation packet is:
D = W min + (W max - W min). (1- pr (i/d))+U (W ran ) ……….. (2)
Where W min and W min denote the minimum and maximum back off timer values, U ( ) is the uniform distribution in [0, W ran -1] and pr (i/d)) can be retrieved from the response table. Note that d contains two parts. The first two terms in Eq. (2) are the deterministic part that relates the estimated distance to the back-off delay value, and the third term accounts for the random part that prevents potential collision when the distances from the target to two or more CHs are approximately the same. The random part is an order of magnitude smaller than the deterministic part.
Operations performed by a volunteering CH:
In order to realize the above mechanism, clock synchronization is required in two respects. First, a CH has to inform sensors of the time when the event takes place so that sensors can match the signature contained in the packet with its buffered data. Second, when a CH sends the localization result to the sink, it has to inform the sink of the time when the event takes place. To avoid the expensive clock synchronization process, we use relative clock values rather than absolute clock values. A CH records the time it detects the event. Before broadcasting the signature packet, the CH calculates the time lag (which includes the processing time, back-off delay and expected propagation delay), and attaches the time lag in the signature packet. When a sensor receives the signature packet, it can infer the time when the CH detected the event.
After broadcasting the signature packet, a CH sets a timer to wait for replies from neighboring sensors. If a sufficient number of replies are received before the timer expires, the CH cancels the timer and calculates the localization result; otherwise, the result is generated upon the expiry of the timer.
C. Sensor Replying
After a sensor receives a signature packet, the first step is to match the signature with its buffered data. The search range can be confined with the use of the time lag information in the signature packet. If the signature is matched, the signal strength in the buffered data (as well as the ratio of the signal strength detected at the CH to that in the buffered data) is calculated.
A sensor Sj does not respond if
Pr (j/r ià j) and r ià j ≥ c1-rmin,
Where c1 is a constant and
rmin is the minimum value of r ià j such that
In the case that a response is to be sent, a similar, random back-off method is used to avoid potential collision of all the replies from sensors to CHi. That is, a sensor Sj delays its reply by a back-off value determined by
D1 = W1 min + (W 1max - W1 min ).(1- Pr (j/r ià j))+ U (W ran )
Where W1 min and W 1max are the minimum and maximum back off values, and Pr (j/r ià j) can be retrieved from the response table.
If by the time the back-off timer expires the sensor overhears reply packets from other sensors, it records the sensor that reports the largest signal strength. When the timer expires, the sensor sends a reply packet only if (i) the signal strength it detected is larger than that carried in any of the overheard reply packets; or (ii) it is one of the Voronoi neighbors of the sensor node that reports the largest signal strength. The two conditions ensure that the set of replies that the active CH will receive includes a reply from a node S j with the largest signal strength, and replies from all S j’s Voronoi neighbors.
D. Reporting Tracking Results
A CH generates the localization result, if either the timer set after the signature packet was sent expires or the CH receives a sufficient number of replies, whichever occurs first. By “sufficient,” we mean the set of replies includes a reply from a node S j with the largest signal strength, and replies from all S j’ s Voronoi neighbors. In this manner, the target is guaranteed to be within the Voronoi cell of Sj. Then, a simple localization approach is used to determine the position of the target: the position of the sensor that reports the largest signal strength is taken as the
estimate of the target.
The scenario that shows how CHs and sensors are deployed in the analysis. Once the localization result is generated, the CH has to send the location and time information of the target to the sink(s).
The CH calculates the time difference between the time instant when it detected the event and the expected time instant when the packet arrives at the next hop and sends the tracking report packet. Each intermediate router accumulates and updates the time lag in the same manner. When the sink receives the report, it can calculate the time when the CH detected the event.
V. CONCLUSIONS
A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a pre-determined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensor information. We show with the use of Voronoi diagram, the CH that is closest to the target is (implicitly) selected as the leader and that the dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations.
No comments: