747 sensor network operation-1-187-13

156 PURPOSEFUL MOBILITY AND NAVIGATION

Collision avoidance area

Figure 3.21 Formation stabilization with collision avoidance is shown.

Avoidance of Moving Obstacles Although we have focused on collision avoidance among controllable agents, our strategy can be adapted to networks with uncontrollable agents (obstacles). Fundamentally, this adaptation is possible because only one agent is required to diverge from its standard trajectory to avoid a collision. Hence, collisions between controllable agents and obstacles can be prevented by moving the controllable agents in a valid direction. Some work is needed to specify the precise conditions needed to guarantee collision avoidance (e.g., we must ensure two obstacles do not converge and that the obstacle does not constantly hinder stabilization). We leave this work for the future.

Simulation We illustrate our strategy for achieving both collision avoidance and formation stabilization using the examples below. Figure 3.21 shows a direct implementation of the collision avoidance strategy developed in this section. The figure verifies that collision avoidance and formation are both achieved but exposes one difficulty with our approach: The agents’ trajectories during collision avoidance tend to have large overshoots because we must make the repulsion acceleration arbitrarily large near the repulsion ball to guarantee that collisions are avoided.

A simple approach for preventing overshoot after collision avoidance is to apply a braking acceleration as soon as an agent is no longer in danger of collision. We choose this braking acceleration to be equal in magnitude and opposite in direction to the total acceleration applied during collision avoidance. Figure 3.22 shows a simulation of collision avoidance, when a braking force is applied after the collision avoidance maneuver. We note that our proof for formation stabilization with collision avoidance can easily be extended to the case where braking is used.

Figure 3.23 shows a more advanced approach to collision avoidance. In this example, each agent is guided along a curve in space, as soon it has detected the presence of another agent in its local sensing ball. Curve following can allow the formulation of much more intricate, and optimized, collision avoidance protocols. Some more work is needed, however, to develop curve-following protocols that can be analytically shown to achieve formation and collision avoidance.

3.5 MODELING AND ENHANCING THE DATA CAPACITY OF WIRELESS SENSOR NETWORKS

157

Collision avoidance area

Figure 3.22 Another protocol for collision avoidance is simulated. Here, we have eliminated overshoot after collision avoidance using a braking acceleration.

3.5 MODELING AND ENHANCING THE DATA CAPACITY OF WIRELESS SENSOR NETWORKS

Jie Lian, Kshirasagar Naik, and Gordon B. Agnew

Energy conservation is one of the most important design considerations for battery-powered wireless sensors networks (WSNET). Energy constraint in WSNETs limits the total amount of sensed data (data capacity) received by the sink. The data capacity of WSNETs is significantly affected by deployment of sensors and the sink. A major issue, which has not been adequately addressed so far, is the question of how node deployment governs the data capacity and how to improve the total data capacity of WSNETs by using nonuniform

Collision avoidance area

Figure 3.23 In this simulation, we achieve collision avoidance by guiding agents along curves in space, once potential collision is detected.

158 PURPOSEFUL MOBILITY AND NAVIGATION

sensor deployment strategies. We discuss this problem by analyzing the commonly used static model of sensors networks. In the static model, we find that after the lifetime of a sensor network is over, there is a great amount of energy left unused, which can be up to 90% of the total initial energy. This energy waste implies that the potential data capacity can be much larger than the capacity achieved in the static model. To increase the total data capacity, we propose two strategies: a nonuniform energy distribution model and a new routing protocol with a mobile sink. For large and dense WSNETs, both of these strategies can increase the total data capacity by an order of magnitude.

3.5.1 Background Information

A WSNET consists of a set of microsensors deployed within a fixed area. The sensors sense a specific phenomenon in the environment and route the sensed data to a relatively small number of central processing nodes, called sinks. Unlike a mobile ad hoc network (MANET) where bandwidth efficiency and throughput are two important metrics, energy conservation is an important design consideration for WSNETs. This is because all sensors are constrained by battery power. Moreover, since sensor networks generally operate at low data rates, signal interference among neighbors is not much of an issue compared to MANET.

Similar to MANETs, researchers have focused on the medium (media) access control (MAC) and network layer protocols for WSNETs [15, 26, 70–75, 83]. Data aggregation techniques also have been studied in [15, 70, 75, 76]. In fact, all of these focus on increasing the energy efficiency of a WSNET, which is represented by the average energy required to transmit a unit of sensed data to a sink. A commonly used model of WSNETs in those studies is the static model in which homogenous sensors are uniformly distributed in the sensed area with one stationary sink. In the static model, we may observe that sensors close to the sink need to forward more data than sensors far away from the sink. Thus, sensors close to the sink exhaust their energy much faster than other sensors. The extreme case occurs with the direct neighbor sensors of the sink, which deplete their energy first. When all neighbors of the sink exhaust their energy, the sink is disconnected from the network, and the lifetime of the network is over. Therefore, the network data capacity of a static WSNET, which is defined as the total amount of sensed data received by the sink, is limited and is mainly determined by the total energy in the neighbors of the sink. Meanwhile, when the lifetime of a network is over, there is an unknown amount of energy left unused. Therefore, it is useful to find the data capacity and energy utilization of a WSNET.

The studies listed above for WSNETs emphasize an increasing energy efficiency, and, therefore, prolonging the lifetime of WSNETs. If we assume that the sink receives sensed data in a fixed constant speed, the lifetime of a WSNET can be measured by the network data capacity. However, from the above discussion and the results obtained in this section, in the commonly used static model of WSNETs energy efficiency is not the most important factor in WSNET operation. Instead, we will show in this section that proper deployment (i.e., locations) of sensors and the sink and energy distribution of sensors have a positive impact on the lifetime (or the data capacity) of WSNETs.

The contributions of this section are summarized as follows. First, we will develop a mathematical model of static WSNETs with uniformly distributed, homogenous sensors and a single stationary sink; next, we will analyze its performance. Performance of a WSNET is evaluated using three metrics: network data capacity, energy efficiency, and

3.5 MODELING AND ENHANCING THE DATA CAPACITY OF WIRELESS SENSOR NETWORKS

159

energy utilization. Unlike the transport capacity of a wireless network discussed in the literature [77, 78], network data capacity of a sensor network is the total amount of sensed data received by the sink. The main observations from this model are that a significant amount of energy is still left unused after the lifetime of the network is over, and the total data capacity achieved is much smaller than the maximum potential data capacity. For moderate size and large WSNETs, after the lifetime of a network is over, there is a large amount of energy left unused, which can be up to 90% of the total initial energy. These results suggest that the static model is not a good choice for large-scale sensor networks. The main reasons for the inefficient energy utilization are the uniform energy level of all sensors and the stationary sink. Therefore, to increase the total data capacity, we propose a nonuniform energy distribution model and a new routing protocol with mobile sink support. Simulation study shows that these two strategies can improve the total data capacity by an order of magnitude of the data capacity achieved in the static single-sink model.

3.5.2 Basic Assumptions

We focus on large-scale, dense networks with several hundreds to thousands of sensors. For these networks, without any loss of generality, we make the following assumptions:

The network area is a fixed W × H rectangular area with width W and height H . N sensors are randomly placed according to Poisson distribution [81, 82] with density λ sensors per unit area. Hence, N = λWH.

All sensors are homogeneous in the sense that all of them have the same amount of initial energy Ps and the same transmission range rs . Each sensor consumes ps quantity of energy to transmit one bit of data.

The locations of the sensors and the sink remain unchanged in the static model.

The sensed phenomenon is randomly occurred in the network area over time.

The sink has unlimited energy and the same transmission range rs as the sensors.

The energy required to transmit data is much more than the energy consumed by CPU processing, sensing, and data receptions. Thus, only the power consumption of data transmission is considered.

Two sensors or a sensor and the sink are said to be neighbors if they are within the transmission range of each other. The average degree g of a sensor is defined as the average number of neighbors of a sensor. Due to the sensors being randomly distributed with Poisson process, we have

g = λπrs2

(3.42)

To deploy a sensor network with hundreds of nodes connected with high probability, say, 0.95, the average degree is at least 4 [79–81]. We assume that the required average degree is not less than 5 to ensure connectivity. When a node senses the phenomenon, we assume that the node chooses the shortest path (with minimum number of hop count) to forward data toward the sink. We ignore the route maintenance overhead and the reason is explained in Section 3.5.3. Due to the low data rate in WSNETs, we assume that data collisions at the MAC level are negligible.