104 PURPOSEFUL MOBILITY AND NAVIGATION

A

B

C

Figure 3.5 Topology of sensing node and three neighboring anchor nodes. Triangulation is done by sensing node using distance measurements from three anchor nodes.

In general, the coefficients k1, k2, k3 are dependent on topology, that is, the relative placements of the neighbors with respect to the sensing node. The upper bound for the sum is infinity (when the three neighbors are collinear), and the lower bound is achieved when the triangles formed by the neighbors with the sensing node are equilateral. We perform an analysis on the topology shown in Figure 3.5. For values of angle θ subtended by the neighbors at the anchor node ( CAD = BAC = θ ) between 365 π (25◦) and 13 π (60◦), it can be shown that k12 + k22 + k32 lies close to 0.2/R where R is the distance between the neighbor and the sensing node. By our algorithm, the locator sends beacon messages when it is either in the cell or in the adjacent cell to the sensing node and therefore R ≤ rT , where rT is the transmission range.

Next, we compute Var(r 2). Consider the error in range measurements and let the upper bound on the relative error be e. This means that if the actual distance between a neighbor and the sensing node is d, the measurement lies between d ± ed. Assume that the range measurements follow a Gaussian distribution. Therefore, almost all the points (99.74% to be exact) lie within µ ± 3σ . Equating, σ = ed/3. The upper bound for this is erT /3. Thus, Var(r ) ≤ (erT /3)2. Then, Var(r 2) = E(r 4) − (E(r 2))2. The higher order expectations can be calculated using the moment generating function of a Gaussian distribution with mean µ and variance σ 2 M(t) = eµt+σ 2 t2 /2. Then E(r 2) and E(r 4) can be derived by differentiating M(t), respectively, twice and four times and evaluating at t = 0. Simplifying, we get from Eq. (3.14) the Probability[Error in location estimate (for the x axis) ≥ Error bound in distance units] as

P(|ux p − E(ux p )| ≥ ) ≤ 1/( p 2) · 0.2e2 R3(2.47 × 10−2e2 + 4.44 × 10−1) (3.15)

For our environment, we pick p = 24 to restrict the error in location estimation in each dimension to 10 m. Note that the above bound can be made much tighter for smaller distances between the neighboring node and the sensing node and for particular topologies. This value of p corresponds to a total of 72 beacon messages by the locator for the nodes in one cell. This means that the number of beacon messages sent out by the locator from each cell (the cell itself and its 8 neighboring cells) is 8.

Once the required number of beacon messages are received by a sensing node, it determines its location. The sensing node then informs the locator of its location. The locator verifies this location using the received signal strength from the node. Then, it assigns the

node to the appropriate cluster. In a majority of cases, the node will be assigned to the cluster to which the locator is coupled. Only if the node has moved far away will it be reassigned to a possibly closer cluster head.

Again considering cell i , the locator sends a beacon message while located in cell i . The cells in Ci1 are ordered according to the metric (Number of nodes in the cell − Distance of the cell from the current position). The complete and incomplete cells are ordered separately with all the complete cells being ordered above the incomplete cells. The locator picks the next cell to visit in order from the ordered list. Next, the cells in Ci1 are ordered, and so on. The movement is stopped when any node in the cell indicates that it has the requisite number of beacon messages.

A constraint for the movement of the locator is that all the ητ beacon messages must be received by a node before it moves. Let the distance between two cells ci and cj be given by δi, j . The locator has sent ηc beacon messages for cell i and in time tc. The locator is currently in cell m and the next cell in the ordered list is cell n. The condition that the locator seeks to enforce is (ητ − ηC ) · δi, j /vl < (ζS − tc). If the condition is violated for cell n, the locator moves to another position within the same cell m and sends another beacon message. This probabilistically assures that all beacon messages are received in the time in which it is useful, that is, between two movements of a node.

3.2.4 Experiments and Results

We perform simulations using the NS-2 simulator [19]. The simulation environment is set up as follows. There are four clusters that are separated over a distance such that any two nodes from different clusters are not able to communicate between each other. Each cluster has a cluster head that collects data from its own cluster. Since the cluster head does not have the capability to send the collected data to the base station, there is a mobile data collector that moves to and collects data from each cluster head. The mobile collector then sends the data to the base station for analysis. The large intercluster distance and the separation from the base station underline the need for a mobile collector as opposed to multiple relay nodes between the cluster heads and the base station.

In each simulation, a cluster sends data, at a constant rate, to its own cluster head. The cluster head stores the data in its buffer until the data collector arrives (either physically or within the energy-efficient communicable distance) and collects the data via wireless communication. The data collector follows a predetermined movement schedule to visit each cluster head. The collector periodically goes back to the base station if it does not have enough energy to serve another cluster head. Each cluster is characterized by the position of the cluster head, the number of nodes in the cluster, and the aggregate data rate of the cluster. In our simulation, we consider heterogeneous clusters. For the simulation, the cluster head is considered nonrotating. Since the geographical spread of the cluster is much smaller than the intercluster distance, we believe this will not have much effect on the results. The four clusters with the positions of the cluster heads and the base station is shown in Figure 3.6. The spread of only cluster 2 is shown. The characteristic of the four clusters is summarized in Table 3.2.

The energy model used for the cluster head is the same as for the radio used in [15, 16]. The energy has two components—one due to the transmit–receive circuitry and the other due to the power amplifier. The latter component depends on the distance over which the data is transmitted. The amount of energy to send n bits of data over a distance d is given by n(ETxRx + EPAd2). The bandwidth for the cluster head to collector communication

106 PURPOSEFUL MOBILITY AND NAVIGATION

Figure 3.6 Topology of four clusters and base station used for simulation.

follows the value for the Berkeley motes [18] of 38.4 kbps. The collector to base station communication happens using GPRS with a range of over 1 km and a bandwidth of 135 kbps. The GPRS energy model also has the two components. The values are substantially different and taken from the energy for the GSM model [20]. The energy model parameters are summarized in Table 3.3.

Fast and Slow Collector In the simulation we use two collector models—a fast collector and a slow collector. The fast collector is based on the Aerosonde model from NASA [21] and the slow collector is based on a commercial mobile robot called the Palm Pilot Robot Kit (PPRK), which was originally designed at Carnegie Mellon University [22] and is currently used in our lab [17]. These collectors are henceforth referred to as the fast collector and the slow collector, respectively. The detailed parameters of these two models is shown in Table 3.4. We assume that the slow collector’s initial energy is 10 times less than the Aerosonde’s to keep the endurance (time between recharges) approximately equal for the two models since for a given travel distance the slow collector consumes approximately one-tenth of the energy of the fast collector. The rationale behind selecting these two models is that the Aerosonde may be used if the data is time-sensitive, such as pertaining to rare event detection by the sensing node, and the mobile robot may be used if there is a budget constraint for the deployment ($40,000 versus $300 per collector in the two cases).

For the simulation, in the slow collector case, the cluster head transfers data to the collector through wireless RF communication for the optimal distance range as calculated in Section 3.2.3. For the fast collector, however, this distance is traversed so fast that we make the simplification that cluster head only transfers data to the collector, once the collector arrives at the cluster head.

Table 3.2 Characteristics of Clusters

the maximum buffer size over all the rounds after throwing out the outliers that lie beyond the 2σ range. The maximum buffer size is the relevant metric since the cluster head will have to provision for a buffer of that size to prevent data loss due to overflow. Throwing out the outliers is needed to eliminate the statistical noise and to draw useful conclusions from the results. The data latency is measured as the average of the time gap between the data generated by the sensing node and the data reaching the base station. We approximate the time the data is generated by the sensing node by the time the data reaches the cluster head. The collector returns to the base station when it estimates its energy will run out before it can reach the next cluster head and collect all its data. The third output parameter is the average time between successive visits of the collector to the base station for recharging.

Experiment Set 1: Fast Collector In the fast collector, we observe the collector has a very high endurance and rarely returns to the base station for recharge. Therefore, the output parameter of average time between recharges is omitted for this set of experiments. The results are presented in Table 3.5.

In the data-rate-based schedule, the buffer size that cluster heads 1, 2, and 3 need is almost similar, but not for cluster head 4. The increasing amount of buffer size in the data- rate-based scenario for cluster heads 1, 2, and 4 compared to the round-robin schedule is because the maximum the number of cluster head(s) that a collector needs to visit before successive visits, to cluster heads 1, 2, and 4 is 9, 4, and 4, respectively. This is higher than the successive visits in the round-robin schedule (3 for all the cluster heads). On the other hand, the gap between successive visits for cluster head 3 is 2, which leads to the decreasing amount of buffer needed. The same reasoning happens in the min-movement scenario since the successive visits to each cluster head are spread farther apart than the round-robin scenario and so is the amount of buffer needed to hold the data. The decrease of average latency in data-rate-based and min-movement compared to round-robin is because both these schedules consider the data rate of each cluster—the higher the data rate, the more often the cluster is visited by the collector. The latency is averaged over the entire data and is therefore improved.

Experiment Set 2: Slow Collector Without Distance Transmission to the Collector In this set of experiments, we consider the slow collector that waits for the collector to arrive at its location before transferring data to the collector. The buffer size, latency, and time between recharges is shown in Table 3.6.

In this result, the buffer size needed by each cluster is higher compared to the fast collector case in Table 3.5. The reasoning is that the collector speed is much slower such that each cluster produces more data between successive visits, which also increases the data collection time of the collector. The frequency of recharge in the round-robin schedule is higher compared to the other two schedules since the collector has to move each time it has finished collecting all the data at a cluster head. In the data-rate-based schedule, there are two occasions in a round where the collector continues staying at cluster head 4 to retrieve more data. This reduces the movement energy consumption of the collector, thus lengthening the time between recharges. In the min-movement schedule, the collector conserves even more movement energy such that the average time between recharging is even higher.

Experiment Set 3: Slow Collector with Distance Transmission to the Collector

In this scenario, the cluster head starts data transmission when the distance between the collector and itself is 100 m and stops the transmission when the optimum distance d is reached. In our case, as shown in Section 3.2.3, d is 14.23 m. Below the optimum distance, the collector continues to move toward the cluster head, and once it arrives at that cluster head, data transmission resumes again.

Since the cluster head is allowed to start data transmission early, this scenario reduces the average data latency on the three schedules, as shown in Table 3.7 in comparison with Table 3.6. There is also a decrease in buffer requirement for the same reason. The percentage of improvement is shown in the Table 3.8.

In Table 3.8, the min-movement schedule has less improvement due to distance transmission because the collector often stays at a particular cluster head for consecutive slots. The fraction of time over which distance transmission happens in the min-movement schedule in relation to the time the collector spends at a cluster head is smaller than in the other movement schedules. Hence, the relative improvement due to the distance transmission is smaller.

The round-robin schedule helps the recharge interval more than the other schedules. This can be explained by the observation that for cluster 1, the lowest data rate cluster, the collector does not always have to physically arrive at the cluster head. In some cases, all

110 PURPOSEFUL MOBILITY AND NAVIGATION

Table 3.7 Results for Slow Collector with Three Different Movement Schedules under Distance Transmission to Collector

the data is communicated to the collector through distance transmission. In that case, the collector directly goes to the next cluster in its schedule (cluster 2). The distance traversed to go to cluster head 2 is less in this case compared to reaching cluster head 1 and then proceeding to cluster head 2. This is thus energy-efficient and lengthens the time period between recharges of the collector.

Experiment Set 4: Locator For the locator, we use a commercial mobile robot (PPRK) [17,22] (same as the one used for the slow collector), equipped with GPS carrying a regular sensor node with capability for short-range RF communication. The locator moves in the cluster with 500 sensing nodes randomly distributed in the cluster spread. All the sensing nodes need to determine their own positions with the help of the locator. The cluster is divided into cells of size 10 m × 10 m, and the size of the cluster is taken to be a square region of dimension 80 m × 80 m, which inscribes the circular cluster region. The locator is

Table 3.8 Improvement for Slow Collector with Distance Transmission to Collector

112 PURPOSEFUL MOBILITY AND NAVIGATION

axis is the time elapsed since the locator started its movement in the cluster. The y axis is the fraction of the nodes in the cluster that have determined their location. The second parameter of interest is the total time measured from the time the locator starts moving in the cluster such that all the nodes in the cluster know their position. For our simulation, this are 109,359.65 s ( 30.38 h). This can be read off from the curve in Figure 3.8 by considering the time for the y-axis value to be 1.0. This time can be looked upon as the worst-case initial latency when none of the nodes know their location to start with. In the steady state, only a few of the nodes will move and an incremental location determination will be needed. For this reason, we are interested in the third parameter, which is the time for a node to determine its location once the locator arrives in its vicinity. This is given by the time to move among the cell in which the node is located and the 8 adjoining cells and broadcast 8 beacon messages from each cell. For our simulation, this time is 2882.39 s (= 0.8 h). This is also the time for which the node will have to be stationary for the location determination to be useful. This number appears high and is due to the slow speed of the locator (0.1 m/s) compared to the transmission range (30 m). In a network deployment, this will be determined by the estimated pause time in the movement of a node and a locator of an appropriate speed will be chosen.

3.2.5 Conclusion

In this section, we have proposed an architecture for energy-efficient data gathering in largescale sensor networks. Some sensing nodes in the network may be passively mobile, which makes the problem more challenging. In the network model under consideration, the sensor field has a large geographical spread, and many of the sensing nodes are far away from the base station. We introduce some special classes of nodes some of which have the capability of controlled mobility, that is, mobility of the form that can be directed by sending control signals. The data collectors have the capacity for moving over long distances, possibly at high speeds for collecting data from the cluster heads and communicating the data back to the base station. The cluster heads aggregate the data from the nodes in the cluster and temporarily store them prior to transmission to the collector. To enable efficient data gathering from the passively mobile sensing nodes, they need to be associated with the closest cluster head and, therefore, need to know their locations. This is enabled by GPSequipped mobile locators that move through the cluster and broadcast beacon messages with location information that helps the sensing nodes determine their position.

In this section, we propose algorithms for motion of the data collectors and the locators. We also propose an extension to the traditional triangulation approach for location determination using mobile locators. The algorithms are analyzed mathematically and simulated to bring out their important characteristics, such as energy consumption, data latency and cluster head buffer requirement (collector algorithm), and convergence time (locator algorithm).

For future work, we plan to consider the movement patterns of the passively mobile sensing nodes in a cluster. We wish to investigate what proactive information broadcast by these passively mobile nodes can benefit the algorithms by making them more informed about the sensor field, such as the density of nodes in a region. We are also investigating the effect of failures of collectors or cluster heads on the data collection. A set of cluster heads can concurrently serve the role. Also cooperation between multiple cluster heads to overcome temporary periods of high data rate is possible. There may be multiple collectors in the network that may work cooperatively in servicing the different cluster heads. Alternately,

there may be a set of collectors for emergency data gathering corresponding to rare events being detected by a sensing node. The mobility algorithm needs to take these classes of collector nodes into account.

3.3 PURPOSEFUL MOBILITY IN TACTICAL SENSOR NETWORKS

Guohong Cao, G. Kesidis, Thomas LaPorta, and Bin Yao

Adding mobility to sensor networks can significantly increase the capability of the sensor network by making it resilient to failures, reactive to events, and able to support disparate missions with a common set of sensors. Mobility in sensor networks may be controllable and hence be used to help achieve the network’s missions. That is, mobility may be “purposeful” instead of being treated as an uncontrollable external stimulus to which the ad hoc networks must respond. To make use of the purposeful mobility, we propose techniques for mobilityassisted sensing and routing considering the computation complexity, network connectivity, energy consumption of both communications and movement, and the network lifetime. We also define utility functions that can capture the benefits of the movement from the perspective of all missions and maximize the capability of the network.

3.3.1 Background Information

Recent advances [23, 24] in hardware design are enabling low-cost sensors that have sophisticated sensing, communication, and computation capabilities to accomplish multiple, disparate missions [25]. These sensors communicate via radio transmitters/receivers to form a multihop wireless network, that is, a distributed wireless sensor network [26]. Sensor networks can automate information gathering and processing and therefore can support many applications (missions) such as target tracking, perimeter defense, homestead monitoring, and intelligent transportation.

As sensors become widely deployed, multiple missions, each with different requirements, may share common sensors to achieve their goals. Each mission may have its own requirements for the type of data being reported, the sampling rate, accuracy, and location of the sampling. As a single sensor network needs to support different sets of missions under different conditions, the requirement on physical sensor locations becomes dynamic.

For example, in target tracking missions, enough sensors should be deployed along the track of the target, whereas in perimeter defense the requirement is to have adequate sensors along a predescribed perimeter. This dynamic requirement on sensor locations cannot be easily met by deploying a large number of sensors since provisioning for all possible combinations of mission requirements may not be economically feasible. More importantly, precise sensor deployment may not be possible, especially in a hostile environment, where sensors are subject to power depletion, failures, malicious attacks, and may change their physical locations due to external force. Therefore, a fixed sensor network has limitations when applied to support multiple missions or when the network conditions change. In such cases, mobile sensors are essential.

Figure 3.9 illustrates an example of using mobile sensors. Initially, fixed sensors indicated by round dots are randomly distributed. Several mobile sensors represented by squares are also deployed in the network. The mission of the network is to monitor the perimeter of a field and track any target that enters the field. This general mission has specific instances in