Sage Journals: Discover world-class research

Abstract

We design and implement a Bezier-based multipath routing algorithm that allows a given source node to send samples of data to a given sink node in large scale sensor networks. Multipath routing can distribute the energy load onto the multiple routes and thus increase the lifetime and quality of the network. It is important to stress the fact that evenly regulating the routing task among the more nodes of the network can also protect a node from failure considering that a node with heavy duty is likely to deplete its power quickly. On the contrary, all the traffic would be shipped along the shortest path routing, corresponding to the heavily congested path case, which in turn leads to overload of the nodes along the optimal routes between the sink and source pair and finally shortens the lifetime of the network. Also, multipath routing can increase end-to-end throughput and provide load balancing. Our view is that minimizing energy consumption while meeting acceptable latency for applications can lead to significant power savings. Our simulation results demonstrate that Bezier-based multipath routing approach significantly outperforms previous SWEEP, Tributaries and Deltas, and the shortest path approaches in terms of lifetime and latency.

1. Introduction

Wireless sensor networks are composed of hundreds or possibly thousands of tiny low-cost nodes which, once deployed in a particular physical environment, can measure various values of interest, perform some limited computation, and communicate with others in order to achieve a desired task in a cooperative manner. Sensor networks can be deployed in large geographic areas to actively monitor a variety of operations ranging from long-term ones (e.g., security alerts) to short-term ones with high degree of dynamics (disaster management). A major research problem, critical to the real world operation of sensor networks, is to design networks that are efficiently and dynamically adaptable to the energy and QoS requirements. The main goal of the proposed research will be to design efficient distributed algorithms for constructing robust and dynamically adaptable routing structures for wireless sensor networks. The algorithms will provide a balance of QoS requirements of the requests and the minimization of the variance of the energy map.

Along with the benefits, wireless sensor networks do bring an impressive set of new challenges for the research community, most of which are rooted, in one way or another, in the following aspects. (1)

The field of operation is often hazardous, in which nodes can become inoperable at any time; the network must be able to adapt to stochastic changes in local topology in order to be able to provide accurate, timely measurements and exhibit an overall robust performance.

(2)

Nodes are battery powered; it is unfeasible to assume for now any means of rechargeability, although solar-powered alternatives have been envisioned. Having a limited energy resource, each sensor's lifetime of operation is bounded by the energy reserves it has and the rate by which it uses it. However, in order to become economically feasible, the wireless sensor network, which has a long amortization period, needs to have a long life span of operation with guaranteed performance. Therefore, novel energy-aware methodologies need to be developed and applied, which requires a whole new approach from typical distributed applications approaches.

(3)

Communication bandwidth is another limited resource that needs to be carefully accounted for. If not, the overall network may exhibit poor performances although each constituent node may act, in a greedy manner, to achieve the best possible performances. Bandwidth awareness is a concept that requires collaboration between neighboring nodes. Problems such as communication scheduling and data reduction (in order to fit the bandwidth limitation) need to be addressed in order for the network to function in a sound manner under load.

(4)

Lastly, scalability of the network is another issue. A given algorithm that is robust, energy-and bandwidth-conscious must also scale with the network size; a typical sensor network may scale to thousands of nodes.

One of the most stringent criteria of performance of a wireless sensor network is its lifetime, which is defined, informally, by the amount of time the network functions with performances above some predefined thresholds. Lifetime maximization problem has been proved to be NP-hard; therefore, methodologies based on heuristic need to be adopted in order to achieve, in a best effort, significant lifetime gains. There are two main approaches to lifetime extension problem: energy conservation (e.g., idle nodes are put to sleep and reduce the amount of time a node participates in communication) and workload balancing. Various techniques have been proposed in literature to reduce either the workload or the energy cost associated with it, for example, in-network data aggregation and multipath routing. Our work targets the lifetime extension problem from the workload balancing aspect. This approach is motivated by the fact that the useful lifetime is not dictated by the residual, aggregated energy resource of the entire network, but by the overall distribution of the energy residues.

In one of our recent work [1–3], we have implemented the split-tree mechanism to prolong the operational lifetime of the nodes, through splitting the root of the tree that can be used concurrently providing many parallel paths from the subroots to the sink node for a given query region, however, yielding better energy consumption than a single path. Motivated by these important results, we feel compelled to study the performance of multipath for each given pair of nodes. When we use the shortest path routing to ship the aggregated results from the root of the tree to the sink and at the same time, if we need to run the continuous query in excess of 100 hours, the energy of the batteries in the nodes along the shortest route between the root-sink pair will drop faster than their neighboring nodes, leading to undesirable effects as longer delays, congestion increases, and lower packet delivery. Finally, those nodes' energy will quickly be depleted, and further shorten the network lifetime. Based on the previous work, we continue to explore the performance of Bezier-based routing in comparison with the other typical multipath routing.

A major research problem, critical to the real world operation of sensor networks, is to design networks that are efficiently and dynamically adaptable to the energy and QoS requirements. The main goal of the proposed research will be to develop energy-efficient and adaptive algorithms for constructing multipath routing.

Multipath routing aims to establish multiple paths between source-sink pair of nodes and thus more sensor nodes to be responsible for the routing tasks in which, in turn, the total traffic are distributed evenly onto multiple routes simultaneously in wireless sensor networks. Multipath routing is typically proposed in order to have backup paths available in case of path failures or to provide the load balancing. Load balancing is of special importance in wireless sensor networks because of the limited bandwidth between the nodes. However, there are also a number of disadvantages to employ multiple paths. In a single path routing, the shortest path is normally selected, and hence, any other paths will typically be longer. It takes much more time for the packet delivery along those multiple paths than the shortest path. Another, we need to consider the complexity and overhead of the multipath routing. In the case of Bezier-based multipath routing mechanism proposed in this paper, maintaining multiple routes to a destination leads to large routing tables at intermediate nodes. Furthermore, the traffic along the multiple paths may interfere with each other. Therefore, the actual performance gain in terms of bandwidth of using multipath over using the shortest path is uncertain. Moreover, how to distribute the traffic over several paths is a key issue in multipath routing. Our Bezier-based multipath routing protocol completely considers that these disadvantages have a significant effect on the performance of the routing.

An important aspect of energy efficiency is performing in-network aggregation while routing data from source sensors through intermediate nodes in the network. Servicing an aggregate query, say $Q_{i}$ , involves disseminating the query from a given sink Si that requested it to all the target sensing nodes relevant to its processing and sending the results from each of the target nodes back to the sink. An effective way of disseminating the queries and gathering the query answer is using a tree structure rooted at the sink. Once the tree is constructed, each of its nodes has a dual role: to forward the answer-sets measured by the children towards the sink and to perform some local aggregation of the data, in order to reduce the communication overhead.

1.1. Motivational Scenario

Army camps that are dedicated to training purposes or for hosting military personnel deployed in geographic regions with insurgent activities typically have a large number of occupants. Furthermore, some regions and buildings may have higher-security restricted access than others. To ensure a certain level of security in such areas, it is desirable that an even larger area, spanning the zone around the perimeter of the camp, is actively monitored by nodes which are capable of sensing the values of various phenomena, for example, audio/sound, low-frequency vibrations, motion, light, temperature, and so forth. Furthermore, those nodes need to organize themselves in cooperative networks composed of multihop routes (based on IEEE 802.15.X). The sensors around the perimeter of the camp constitute an active distributed database that monitors the values with various queries of interest as well as detecting the occurrence of events of interest. Similar situations arise around air bases and naval bases/ports, and in some cases the security monitoring around the perimeter may rely on/under water sensors. In these settings, additional efforts are needed to ensure QoS bounds on the routing structures because the individual sensors, even if anchored, are subject to motion due to the waves/tides.

As an example of the security-related behavior, when the data from the audio sensors and vibration sensors indicate that a mobile object is continuously moving along (within less than 1 mile distance from) the perimeter of the restricted area, for more than 80% of the time within 10 minutes, a change of the type increases the monitoring to security-level-1 should be steered to increase their sampling frequencies (and, potentially, even video sensors will zoom towards the targeted area). Moreover, a new query may be issued which will require the sensors to detect whether there are objects that are continuously moving towards the object that has been detected, the security personnel is notified, and their vehicles are guided towards the expected location of the potential intruders.

The scenario above illustrates the need for dynamic adaptability of the individual sensor nodes and the networks as a whole, for the purpose of ensuring some QoS in potentially escalating threats. An equally important aspect is that even under regular (no-threat) operational mode, adaptability is an important feature: for example, when a prolonged absence of a heartbeat-signal indicates the loss of a node, the topology of the network should automatically reconfigure itself, in order to ensure the desired QoS level. When a new query pertaining to a given spatial region is posed, some of the nodes, which will have to sample the data and aggregate it and route it towards that query's sink-node, may have already been involved in managing other queries. Consequently, they will have to adjust their behavior to incorporate the newly received role and (1) ensure that they provide a sufficient QoS level for both requests and (2) ensure that this is done in a manner that will extend the network's lifetime as much as possible. Observe that the need for cooperative behavior of the heterogeneous nodes need not be constrained to spatially close regions. For example, in an army camp, some of the buildings may be equipped with sensors that monitor the status of the electricity installations, as well as temperature sensors and RFID sensors. In case a sharp and continuous increase of the average temperature reading is observed for more than 2 min in any area of the building which is less than 400 ft², the sampling frequency of the sensors monitoring the electricity installation in the building should be tripled, and the motion sensors in the perimeter zone of the camp entities are continuously moving towards the camp.

In case of a large-scale disaster, either due to a natural phenomenon (e.g., earthquake, fire) or an attack (e.g., bombing, poisonous gases emission), it is likely that many of the deployed sensors may be destroyed and unusable. The issue now is to intelligently use the set of sensors that may still be available in the camp. Clearly, this decision will be based on the types of requests expected to be managed by the sensor network in the immediate future following the occurrence of the disaster, which will be dictated by the authorities in charge and their demands.

The rest of the paper is organized as follows. In Section 2, we provide related work into the area of multipath routing for wireless sensor networks. We model the query component and formulate Bezier-based the routes problem in Section 3. Section 4 discusses route establishment, Bezier curve theoretical model, and data transmission of the Bezier-based multipath routing. Based on simulation results, Section 5 presents a detailed analysis of load balancing, end-to-end delay, and the packet delivery rate metrics for four routing mechanisms. Section 6 concludes the paper.

2. Related Work

There have been extensive study on routing in wireless networks in recent years. Among various metrics used for evaluating the routing quality, the most common one is probably the number of hops on the routing path. Two of the most widely used are the dynamic source routing (DSR) [4] and the ad hoc on-demand distance vector (AODV) [5] protocols. AODV and DSR are both on-demand protocols. In DSR, the source includes the full route in the packets' header. The intermediate nodes use this to forward packets towards the destination and maintain a route cache containing routes to other nodes. However, as opposed to DSR, which uses source routing, AODV uses hop-by-hop routing by maintaining routing table entries at intermediate nodes [6]. Please refer to the surveys [7] and the references therein. On the other hand, energy-aware routing algorithms, which try to maximize the network survivability, have attracted a lot of interests [8–21]. The energy aware metrics, such as “maximize time to partition” and “minimize maximum node cost,” were first proposed by Singh et al. [22]. Chang and Tassiulas [23, 24] used a flow augmentation algorithm and a flow redirection algorithm to balance the energy consumption on different nodes.

Various aspects of the problem of routing in wireless sensor networks settings have received considerable attention, due to the fact that the communication has the largest impact on the depletion of the batteries of the sensor nodes. Research on multipath routing protocols is to provide improved load balancing and route resilience as compared with single-path routing, which in turn preserves the residual energy of nodes and balances the consumed energy to prolong the lifetime of the network.

The concept of using multiple paths for routing purposes in sensor networks is well studied. Results based on the directed diffusion approach, which use the simple flooding algorithm, where every node in the network broadcasts each new message to all of its neighbors are presented in [25]. In addition to constructing disjoint paths that do not intersect, the work also considers braided paths which may intersect. Although the motivation is similar to our prolonging lifetime, the work is more focused on resilience to failures and it proposes routings for which the decisions are made locally. Our work is, in a sense, complementary because although we consider multiple routes, we also explore the context-aware routing structures among a family of routes in the vicinity of the source/sink node for the purpose of extending the network's lifetime while ensuring QoS level of the data genertaion and delivery delay.

Algorithms for local construction of energy-efficient topology are presented in [26] where plannar spanning structures with guaranteed stretch factors are presneted. The structures utilize concepts such as Yao graphs and Gabriel graphs [27] to enable each node to make local decisions about selection of neighbors and communication power. Trajectory based forwarding (TBF) was introduced in [28] and enables a routing protocol where the nodes locally decide about forwarding of the packtes, based on a prespecified trajectory. Further generalization is provided in [29], which introduces the TBF+ concept, which uses polynomial curves for the trajectories (e.g., an ellipse). Using curve-fitting and the information about the energy of a particular node, TBF+ forces the trajectories to pass through points with higher energy reserves. However, this research did not consider alternating trajectories in the context of network lifetime. A form of alternating the delivery of the packets among individual nodes in the vincinity (as a function of the distance from) of a given sink is presented in [30].

The results in [31] demonstrated that interference due to geographic proximity can be tackled and some controlled form of concurrent transmission can be achieved from a set of source nodes towards a given sink. The work provided a formal algebra for specifiying the concurrency/serialization of the routing. We plan to use these ideas for specifying desirable properties of the routing structure.

In wireless sensor networks, the energy of communication cost is often several orders of magnitude higher than that of computation cost. Data aggregation in the network can greatly reduce the packet transimission and thereby lower the communication cost. So in-network data aggregation is considered an effective methods to minimize the communication cost. The inherent redundancy in raw data collected from the sensors can often be eliminated by in-network data aggregation. In addition, such operations are also useful for extracting application specific information from raw data. To conserve energy for a longer network lifetime, it is necessary for the network to support high incidence of in-network data aggregation. Data aggregation has been studied extensively [32–37]. The main motivation is to minimize the transmission of packets containing individual measurements whenever the semantics of the application needs a summarized picture of the environment, for example, a weighted sum of the signals, and allows for functional decomposition when calculating the statistical values. When the data based on the actual measurements is categorical, even pattern identification techniques can be used for aggregation. Important parameters that impact data aggregations in wireless sensor networks have been addressed from the perspective of database-like query processing and, recently, the energy efficiency of node clustering with data aggregation trees has been studied.

3. Query Model and Problem Formulation

3.1. Query Model

Users need to be able to interact with the sensor network, typically by connecting to a sink node and submitting queries of interest for which the network must provide accurate answers in a timely manner. While the most common, standard query specification language is SQL, which is typically used in database systems, it has also been adopted in wireless sensor network application based on the abstraction that the network represents, in fact, a largely distributed database system. However, specific aspects that distinguish a typical database from a sensor network infrastructure brought modifications to SQL and the most recognized SQL-specification for wireless sensor network is TinySQL. Regardless of the query specification language, a wireless sensor network needs to provide mechanisms for query processing that are both energy and bandwidth conscious. For example, as we have shown, it is imperative, for resource usage efficiency, for a sensor network to implement a triggering (or similar) mechanism in order to better implement monitoring queries (continuous queries).

Given a goal of allowing users to pose declarative queries over sensor networks, we adopt a SQL style query syntax. The typical scenario is as follows: a network user connects to one of the sink nodes, formulates, and submits a query of the following form:

Q: SELECT: ALL/MIN/MAX/AVG (measurement)

FROM: region $(R_{1} (x_{1}, y_{1}, \dots, x_{n}, y_{n}))$

WHERE: condition (measurement)

FOR: lifetime

SAMPLE EVERY: sampling interval.

$R_{1}$ represents the geographical bounds of the region from which the samples for the query are to be collected from. If $R_{1}$ is not explicitly specified, the query region means the entire sensor network deployment area. Sampling interval indicates the frequency each node must acquire the measurements and ship the data towards the sink. The sensor must stop sensing and sending the data towards the sink node after the lifetime period expires. There are two possible situations based on the query Q which is handled at the sink node. (1)

The sink node is physically located within the sampling region $R_{1}$ .

(2)

The sink node is outside of region $R_{1}$ .

In our previous work, our approach is designed to exploit the root-load balancing in the scenario where this is readily possible in the situation where the sink node is physically located outside the region $R_{1}$ . Fortunately, this case is more common in large and very large sensor network applications, where the user is likely to be interested to sample remote areas of the network, rather than the entire wireless sensor network. Figure 1 gives an illustration of this case that we will exclusively consider. Therefore, we will have to construct point-to-point routes from the aggregation root node, which is situated inside the sampling region, to the ultimate destination, the sink node. The aggregation results should be shipped along with these paths.

Figure 1

Sink node is physically located outside the sampling region.

3.2. Setting

Given a collection $S = {S_{1}, S_{2}, \dots, S_{n}}$ of possibly heterogeneous sets of sensors which are deployed in a geographic area of interest, pending requests can be of two basic types: (1)

continuous queries, which pertain to raw data or a function of it, from a subset of the sensors over a given time interval (instantaneous queries, which require a “snapshot” of the values at a given time-instance, will be treated as a special case of continuous queries),

(2)

notifications, which pertain to detection of an occurrence of a given event, based on the values measured by the sensors.

A particular request may involve only a subset of the nodes that are determined based on their individual semantics, and they may originate in different sinks. The information of interest may be the data measured by an individual sensor node or a group of nodes in a geographic region defined either explicitly or implicitly in the semantics of the aggregate statistics amid a group of sensor nodes. Typical applications using aggregates are the average temperature, the average concentration of a hazardous gas/toxic in an area, the average or minimum remaining battery life of sensor nodes, the count of persons/vehicles in some area, and the maximal noise level in a group of acoustic sensors, to name a few. The operations for computing basic aggregates, such as average, max/min, and sum and count, could be further adapted to more sophisticated information processing operations.

An exemplary instance of a problem setting addressed in this research is illustrated in Figure 1. Assume that initially there were two queries, $Q_{1}$ posted at $t_{1}$ and $Q_{2}$ posted at $t_{2} > = t_{1}$ , that pertain to the values read in some geographical regions. Their different semantics required different routing structures towards the respective sink-nodes. For $Q_{1}$ the routing tree is constructed and rooted at the sink_1 with different paths towards the nodes inside the region. The nodes inside the region for the query $Q_{2}$ have organized themselves as a tree, and there is one route between the root of that tree and the respective sink_2. Assume that, at some future time instance $t_{3} > t_{2}$ , another query $Q_{3}$ was posted by the sink_3, which pertains to a region intersecting both regions of the older queries $Q_{1}$ and $Q_{2}$ . The question is to construct the routing structure for $Q_{3}$ , given the sink_3 while taking into account that some nodes may participate in measuring and/or routing for the other two older queries and considering the demands of the timely delivery of the data with certain QoS assurances. Another question is how all these nodes will adjust their aggregation and samplings without deteriorating the desired QoS assurances.

Long-term queries represent a significant stress factor for the network, in energy terms, as they contribute towards the imbalance of the spatial distribution of the energy map. Due to the energy depletion of the sensor nodes that are involved in servicing queries, the overall network's lifetime may be affected, if it is defined, for example, in terms of the overall connectivity. Typically, long-term queries require periodic sampling readings of the desired values from a set of nodes (sources) and the transmission of them to the nodes where these particular queries originate sinks. In the simplest form, a sink node requires readings from a single source, which may be either the sole producer of the data or represent an aggregation node of data from a surrounding region of interest. When a long-term query is dispatched in wireless sensor networks, multipath routes will be constructed over which data streams are transmitted towards a common sink node. In the consequence, from the energy-perspective, of long-lived data-streams in the “transit” area of the network: an energy “gap” may develop due to perusal of a subset of relay nodes situated in that area. This may lead to the appearance of holes in the network and to the loss of connectivity. Energy depletion may be even more severe in the vicinity of the sink node itself. Another observation is that when multiple routes are related to a single sink, the nodes in its vicinity tend to deplete at a higher rate than distant nodes, not only due to their increased utilization, but also due to increased frequency of collisions and retransmissions of data-packet pertaining to spatially close data streams.

3.3. Problem Formulation

Sensor nodes that are outside the sampling region are also important as they might be used in data-relay duties, making the connection between the producer, in the sampling region, and its consumer, the sink node. For each source-destination pair, a single (shortest) path is always discovered and used for data transmission; as seen in Figure 1, the aggregated information will be sent to the sink through the bold intermediate nodes. Obviously, in wireless sensor network, with a high density of nodes the shortest paths connecting any pair of nodes tend to be very close to the line segment connecting those two nodes. Hence, that area close to the line segment will be very likely to develop hot spots, which is the situation we are trying to avoid in the first place. The fact that these nodes are overused is one of the major causes for hot spots. Hot spots in the deployment region will also affect the nodes' coverage because the nodes in the spots will likely cease to operate. This paper provides a new multipath protocol which is based on Bezier curves for mitigating the sensor network hot-spot problem, considering load balancing as well as quality of service.

3.4. Goals

The running cost of the routing structures depends on two factors: the energy cost for transmission between the adjacent tree nodes (parent and children) and the cost of aggregation that is captured by the aggregation function f; if information from j sources is routed over a single link, then the total information that needs to be transmitted is $f (j)$ . For example, if f is a constant (perfect aggregation, as in finding the minimum, average, etc.), then it can be demonstrated that a minimum cost spanning tree or a minimum cost Steiner tree is the optimal aggregation tree. On the other extreme, if f is the identity function, then the optimal aggregation tree is the shortest path tree. Regardless of the nature of the aggregation, the two important goals are reducing the total transmission cost and thus the energy consumption in the individual sensor nodes and maximizing the network lifetime by achieving as much load balance as possible while routing. Thus some nodes do not run out of energy while a significant amount of energy remains in other nodes. Obviously, multipath routing methods can obtain load balancing.

4. Bezier-Based Multipath Routing Algorithm

4.1. Route Establishment

We assume that each node knows its location and the location of its neighbors. This simulator provides us with the heartbeat algorithm, which is already implemented and executed in the first hour of the simulation, and finds the neighbors for us.

Multipath routing protocol can try to find node disjoint, link disjoint, or nondisjoint routes. Node disjoint routes, also known as totally disjoint routes, have no nodes or links in common. Link disjoint routes have no links in common but may have nodes in common. Nondisjoint routes can have nodes and links in common [6]. Since we assume the whole topology is known, finding node-disjoint multiple paths is not a difficult task. Figure 2 illustrates a family of four Bezier curves that can be used as multiple routes for a given (sink, source) pair, in addition to the shortest path, that is, the direct line segment between the source and the sink. Figure 3 shows an example of how to construct Bezier-based multipath which is node-disjoint routes given a source-sink pair of nodes. As can be seen in this Figure, that multipath from source to sink does not interfere with each other except that they share the resources at source and sink. To the best of my knowledge, even if the multiple paths are node-disjoint, transmissions along the routes may interfere if some nodes among the routes are in the same collision domain. When we establish multiple paths, it is important to establish paths that are as independent as possible to ensure the least interference between the paths.

Figure 2

Multiple routes with Bezier curves.

Figure 3

Bezier-based multipath routing model.

The algorithm for constructing the routing structure should be as follows. For a given source-sink pair of nodes, the sink will unicast on a shortest path routing (along a straight imaginary line) the query request to the source node. Subsequently, based on the query specification, referring to Figure 3, we will draw a segment orthogonal to source-sink line segment. We will split the segment in k places, which will correspond to k intermediate destination points (breakpoints) of the paths between the sink and the source. The distance between two consecutive paths on the line which is orthogonal to the source-sink segment will be equal. From a set of control points, not only one curve can be computed, but an entire family of curves can be also generated. Therefore, we will establish Bezier-based multipath routing to offer more opportunities for regulating the traffic over the network.

The theoretical principle which is adopted in our approach relies on the concept of Bezier curves, developed by Paul de Casteljau (1959) and independently by Pierre Bezier (1962) [38]. In its general form, a Bezier curve of a given set of $n + 1$ points: $P_{i} (i = 0,1, 2, \dots, n)$ , and a parameter $t \in [0, 1]$ , is defined as

\begin{matrix} p (t) = \sum_{i = 0}^{n} P_{i} B_{i, n} (t), \end{matrix}

(1)

where

B_{i, n} (t)

Bernstein polynomials are defined as

\begin{matrix} B_{i, n} (t) = \frac{n!}{i! (n - i)!} t^{i} {(1 - t)}^{n - i} . \end{matrix}

(2)

Sum to one for any t in $[0,1]$ ,

\begin{matrix} \sum_{i = 0, \dots, n}^{} B_{i}^{n} (t) = 1 . \end{matrix}

(3)

For 3 control points, $n = 2$ ,

\begin{matrix} p (t) = (1 - t) 2 p_{0} + 2 t (1 - t) p_{1} + t^{2} p_{2} . \end{matrix}

(4)

For 4 control points, $n = 3$ ,

\begin{array}{l} p (t) = {(1 - t)}^{3} p_{0} + 3 t {(1 - t)}^{2} p_{1} + 3 t^{2} (1 - t) p_{2} + t^{3} p_{3}, \\ p (t) = (- t^{3} + 3 t^{2} - 3 t + 1) p_{0} \\ + (3 t^{3} - 6 t^{2} + 3 t) p_{1} + (- 3 t^{3} + 3 t^{2}) p_{2} + (t^{3}) p_{3}, \\ p (t) = (- p_{0} + 3 p_{1} - 3 p_{2} + p_{3}) t^{3} + (3 p_{0} - 6 p_{1} + 3 p_{2}) t^{2} \\ + (- 3 p_{0} + 3 p_{1}) t + (p_{0}) 1 . \end{array}

(5)

If we regroup the equation in terms of exponents of t, we get it in the standard cubic form. This form is very good for fast evaluation, as all of the constant terms $(a, b, c, d)$ can be recomputed. The cubic equation form obscures the input geometry, but there is a one-to-one mapping between the two and so the geometry can always be extracted out of the cubic coefficients:

\begin{array}{l} p = a t^{3} + b t^{2} + c t + d; \\ a = (- p_{0} + 3 p_{1} - 3 p_{2} + p_{3}), \\ b = (3 p_{0} - 6 p_{1} + 3 p_{2}), \\ c = (- 3 p_{0} + 3 p_{1}), \\ d = (p_{0}), \end{array}

(6)

\begin{array}{l} p (t) = [\begin{bmatrix} t^{3} & t^{2} & t & 1 \end{bmatrix}] \cdot [\begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix}], \\ [\begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix}] = [\begin{bmatrix} - 1 & 3 & - 3 & 1 \\ 3 & - 6 & 3 & 0 \\ - 3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}] \cdot [\begin{bmatrix} p_{0} \\ p_{1} \\ p_{2} \\ p_{3} \end{bmatrix}] . \end{array}

(7)

We can rewrite the equations in matrix form. This gives us a compact notation and shows how different forms of cubic curves can be related. It is also a very efficient form as it can take advantage of existing $4 \times 4$ matrix hardware support. For example, given three points $P_{0}$ , $P_{1}$ , and $P_{2}$ , a quadratic Bezier curve is the path traced by (4) as shown in Figure 4.

Figure 4

Construct a Bezier curve from given three points.

The curve passes through the first, $P_{0}$ , and last vertex points, $P_{n}$ . The tangent vector at the starting point $P_{0}$ must be given by $P_{1} - P_{0}$ and the tangent vector $P_{n}$ must be given by $P_{n} - P_{n - 1}$ . The properties of the Bernstein polynomials ensure that all Bezier curves lie in the convex hull of their control points. Hence, even though we do not interpolate all the data, we cannot be too far away. Figure 5 describes convex polygon formed by connecting the control points of the curve. Curve resides completely inside its convex hull.

Figure 5

Curve resides completely inside its convex hull.

We have relied on the flexibility of the Bezier curves in order to overcome some of the cause of premature lifetime termination: lack of appropriate workload balancing in the most critical of the network around the sink and source nodes. By using the Bezier curve as the trajectory model, we are able to control the coverage of the sink/source nearby nodes implicated in the routing and attain, in a practical setting, a near 100% utilization of them. Figure 3 shows the routing coverage, for workload balancing, by means of trajectory-based alternating routes, in comparison with the ones which provide routes that approximate, to some degree, the shortest path routing.

The route's information, which is represented through a Bezier curve, must be transmitted from node for the routing purposes. A node, however, needs only to communicate the coordinates of the control points in order to be able to generate an entire Bezier curve, no matter its shaped and length. This property will save both time and energy, a clear advantage of using parametric curves such as Bezier. Moreover, not only one curve can be computed from a set of control points, but an entire family of curves can be also generated, based on the affine property of Bezier curves, which will prove benefit when managing multiple routes between two source-sink points. Bezier curves add flexibility to the routes. If we consider two fixed endpoints, the shape of the curve can be adjusted by using the remaining control points. Figure 6 shows the type of shapes Bezier trajectories can take by simply relocating these control points given the source-sink endpoints $p_{0}$ and $p_{1}$ .

Figure 6

Linear, quadratic, and cubic.

Route construction: firstly, the sink needs to specify its tolerance for the time delay of the packets, for example, with respect to the delivery time along the optimal routes, which will be used to determine the length of the Bezier curve corresponding to the alternative route furthest from the optimal one. Secondly, the sink needs to determine the control points (i.e., the shape) of the curve and the values of two parameters: the discretization level for approximating the curve with a plotline and the discretization level m of bringing its control points from their initial positions, to their final position along the optimal route. Given a particular Bezier curve, we can utilize it as a route to relieve the load of the nodes that participate in the shortest route between the sink and the source. However, one Bezier curve enables the utilization of only a small subset of nodes between the source and the sink nodes. On the other hand, the degree of lifetime extension is proportional to the total number of sensor nodes that can share the load and serve on alternate paths. Hence, a larger family of curves between the source and the sink is desirable. However, in order to construct this family, we have to guarantee that these multipath routing are nonintersecting while ensuring sensing coverage and connectivity.

Once the set of alternative routes have been constructed, the source needs a policy for selecting the route that should be used for transmitting a given data value. Assuming that the counter-clockwise direction is a positive one, the set of alternating routes can be enumerated as $S = [1,2, \dots, k]$ , where “ $k / 2$ ” corresponds to the optimal route (the shortest path). The policy of alternating among the routes amounts to selecting the permutations of S; for example, the source may randomly select a route or use the original sequence S. However, this may incur packets collisions due to interference among the nodes along spatially close routes because, with a high sampling, frequency, spatially close nodes will be employed for different routes which, during one period, correspond to the following sequence. We call this the constant mid-distance alternating of routes, and it is illustrated in Figure 2 by the arrowed plotline. The algorithm which computes points on a Bezier curve is implemented as shown in Algorithm 1.

Algorithm 1: Construction Bezier curve routes.

Input: $P, n, u$

Output: C (a point) ^*/

for ( $i = 0$ ; $i < = n$ ; i++)

$Q [i] = P [i]$ ;

for ( $k = 1$ ; $k < = n$ ; k++)

for ( $i = 0$ ; $i < = n - k$ ; i++)

$Q [i] = (1.0 - u) * Q [i] + u * Q [i + 1]$ ;

$C = Q [0]$ ;

4.2. The Analysis of Finding Multiple Node-Disjoint Paths

Due to the independence of the paths, disjoint paths have received considerable attention in the recent literature. The main reason is that disjoint paths offer certain advantages over nondisjoint paths. When using nondisjoint routes, a single link or node failure can result in multiple routes to fail while in node or link disjoint routes, a link failure will only cause a single route to fail. What is more, both the nodes and the wireless links are error prone, which leads to multiple paths that share those nodes and links to fail in nondisjoint paths. Hence, node-disjoint paths can provide the highest degree fault tolerance.

A number of algorithms have been proposed in order to find disjoint paths in wireless sensor networks [39–44]. There are two types of disjoint paths: link-disjoint and node-disjoint. Obviously, node-disjoint paths are also link-disjoint paths. Both node-disjoint paths and link-disjoint paths can improve the reliability and security. For some applications, node-disjoint paths are preferred considering the security.

Many algorithms to find node-disjoint paths make use of request/reply cycles. Typically, a source node initiates a route discovery procedure by broadcasting a route Request packet, and then this ROUTE REQUEST message is flooded to the entire network. Because this message is broadcasted, duplicate packets are received by intermediate nodes. These duplicate packets are not dropped by intermediate nodes but recorded in a RREQ table which keeps track of all the neighbors from which a RREQ is received and the hops away from the source [45]. When a RREQ reaches the destination, the destination creates a RREP and sends RREP back to the last hop node for all received RREQ packets. An intermediate node forwards a received RREP packet to the neighbor in the RREQ table that is along the shortest path to the source. In order to ensure that a node does not participate in more than one route, whenever a node overhears its neighbor's transmission of a RREP message, it deletes that neighbor from its RREQ table. The discovered routes in such a way must be node-disjoint paths.

Contrary to the above general algorithm, our Bezier-based multipath algorithm to build node-disjoint routes does not generate too much RREQ/RREP packets and then increases the routing overheads. Instead, we fully make use of geometrical knowledge to discover routes. According to Figure 3, all the coordinates of k breakpoints can be more easily calculated, in a segment orthogonal to source-sink line segment. In each of $k - 1$ surrounded regions, we only construct one route from the source node to the sink node. Those intermediate nodes in one route are selected in a way that they should be closest to Bezier curves. This is easily explained by the fact that it takes more time to deliver packets along the path farther away from the source-sink line segment. Multiple paths may present differences in the end-to-end delay of each path. Such scenarios require that data coming from different flows needs to be buffered till the flow from the path with the highest delay arrives for reordering the data correctly. This solution poses another problem, since high speed memory is extremely expensive, and therefore we should minimize the differential delay. In our simulation, we do not need to consider packet reordering. Obviously, the k-1 routes we build have no nodes or links in common. The formulas through which we compute distance and coordinate can be, respectively, expressed as

\begin{matrix} x_{0} = \frac{(x_{1} + x_{2})}{2}, y_{0} = \frac{(y_{1} + y_{2})}{2}, \\ d = \sqrt{{(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2}} . \end{matrix}

(8)

Wireless sensor nodes are deployed in the 2D geographic area which stands for each node and has fixed pair coordinates $(x_{i}, y_{i})$ , corresponding to the X and Y axis. Each node is capable of obtaining its location coordinates at run time, either by means of hardware system, for example, a GPS device, or by performing a searching location algorithm, such as the abovementioned heartbeat algorithm [46–49].

4.3. Data Transmission

Once the set of routes have been constructed, the source needs a policy for selecting which particular route should be used for transmitting a given packet. Some multiple paths are used as a set of candidate alternate routes while our approach of multipath is used simultaneously, which distributes the load onto multiple paths evenly; that is, the total number of packets on each route is equal. Obviously, those longer length paths have longer delay, and in consequence, less traffic should be dispatched there and meanwhile traffic should distribute more different paths in order to achieve a minimum mean delay for the whole network. In next section we will discuss the delay of these two routing approach.

Once multiple routes have been constructed, there exists a multipath routing table to record their next hop nodes. The source and intermediate nodes check their routing tables, update, delete, and replace the routes which contain the broken link and dead nodes and rearrange the routing tables accordingly. If a route to the destination is still required, it will build a new route process. Routes are also deleted from the routing table if they are unused for a certain amount of time.

4.4. Impact of k

We should not ignore the fact that nodes in wireless sensor networks communicate through the wireless medium. If a shared channel is used, neighboring nodes must contend for the channel. When the channel is in use, neighboring nodes may be blocked from receiving from other sources. Nodes within transmission range of each other are said to be in the same collision domain. If the distance between any two neighboring routes is within the same collision domain of two neighboring nodes and even if the traffic is transmitted along the node-disjoint paths, the quality of the neighboring transmissions may be degraded due to interference. Therefore, when we construct k Bezier-based multipath routes, we have to ensure the distance between two consecutive paths is much larger than the transmission range.

Path reliability is the product of the link availabilities along the path, assuming the link availabilities are independent. We assume the end-to-end reliability is p, where $p_{k}$ is the path reliability of a path, k is the set of all paths, and then p can be expressed as

\begin{matrix} p = 1 - \prod (1 - p_{k}) . \end{matrix}

(9)

Notice that the reliability is higher than any of the path reliabilities.

5. Performance Evaluation of the Bezier-Based Multipath Routing

To verify the algorithm in more realistic conditions, the experiment is implemented on Mica2 Motes and tested in SIDnet-SWANS. Our simulation setting is as follows. We create 500 nodes uniformly deployed in a $2 \times 2$ km² area, which use the heartbeat node discovery protocol in order to determine the neighbors. Nodes are homogeneous, sharing the same configuration: 19.2 kbps transmission/reception rate on Mac 802.15.4, 10 s time-to-sleep interval, max message size 36 bytes, and power consumption characteristics based on the Mica2 Motes. A small battery powers each node, with an initial capacity of 35 mAh, which, given the power consumption characteristics as summarized in Table 1, is expected to power a node for a few tens of hours, depending on the load. We randomly pick up one pair of nodes as source-sink nodes from the physical terrain, and for simplicity, we do not consider the characteristic of the mobility of the nodes. In order to show the significant advantages of our proposed methodology, we compare the performance with three multipath routing protocols in different aspects: (1)

the shortest path routing,

(2)

Tributaries and Deltas (TD) [34],

(3)

sweep [36].

Table 1

Energy characteristics of Mica2 Mote.

State	Based (mA)	Energy requirement (mJ/ms)
Sensing active	9	0.05
Sensing passive	0	0
CPU active	9	0.025
CPU idling	0.01	$4.5 * 10^{- 5}$
Radio transmitting	28	0.08
Radio receiving	9	0.04
Radio listening	2	0.008
Radio sleeping	0.5	0.0016

As shown in Figure 7(a), the shortest path routing algorithm minimizes the total energy the network consumed but does not balance the loads on different nodes. So a node could easily be overloaded under the shortest path routing and thus could quickly extinguish their batteries. So it is advisable to minimize energy consumption in these nodes. If we wish to achieve the shortest path routing, it is appropriate to use the greedy method of sending the packet to the furthest reachable node in the right direction. However, this may create heavily loaded nodes and greedy problems. On the other hand, if we adopt the greedy strategy of forwarding a packet to the node with the lightest load, it may result in extremely long path. Figure 7(b) shows that Tributary-Delta combines the advantages of the existing tree- and multipath-based approaches by running them simultaneously in different regions of the network, because both tree-based and multipath-based structures have their strengths and weaknesses. This approach presented schemes for adjusting the balance between tributaries and deltas in response to changes in network conditions. Tributary-Delta aggregation scheme makes full use of the efficiency and accuracy of small trees under low loss rates with the robustness of multipath routing. Specifically, part of the query region runs tree scheme while at the same time the rest of the region runs multipath scheme. TD methodology presents schemes for adjusting the balance between Tributaries and Deltas in response to changes in network conditions by switching switchable M vertices (multipath nodes) to T vertices (tree nodes) or by switching switchable T vertices (tree nodes) to M vertices (multipath nodes). Sweep method traverses the network, passes over each node exactly once, and performs the desired operation(s). This method does not require global information about the sensor field such as node locations. Instead, a potential function is computed over the network during the early preprocessing stage and their gradients direct the sweep process. The sweep scheme adopts only local operations to advance the wave front and operates asynchronously. The gradient information provides a local ordering of the nodes that helps reduce the number of MAC-layer collisions with the advance of the sweep. The potential function is computed by the Gauss-Seidel iteration in which each node repeatedly sets its potential to the average of the potentials of its neighbors. According to the potential value at each node, the sweep may decide which nodes can be invited to the sweep process. The current computation of the potential function converges much slowly. Please see [34, 36, 50] for the details.

Figure 7

(a) The shortest path routing and (b) Tributaries and Deltas (TD) protocol.

We evaluate the performance according to the following metrics.

(i) Average End-to-End Delay. The end-to-end delay is the average time for all surviving data packets from the source to the destination. This includes all possible delays caused by buffering during route discovery latency, queuing at the interface queue, retransmission delays at the MAC, and propagation and transfer times. It can be defined as

\begin{matrix} D = \frac{1}{N} \sum_{i = 1}^{S} (r_{i} - s_{i}), \end{matrix}

(10)

where N is the number of successfully received packets, i is unique packet identifier,

r_{i}

is time at which a packet with unique id i is received,

s_{i}

is time at which a packet with unique id i is sent, and D is measured in ms. It should be less for high performance.

(ii) The Packet Delivery Fraction. The packet delivery fraction represents the percentage of the number of successfully received data packets at the destination to the number of data packets created by the source. The ratio of the data packets delivered to the destinations to those generated by the sources. Mathematically, it can be expressed as

\begin{matrix} P = \frac{1}{C} \sum_{f = 1}^{e} \frac{R_{f}}{N_{F}}, \end{matrix}

(11)

where P is the fraction of successfully delivered packets, C is the total number of flow or connections, f is the unique flow id serving as index,

R_{f}

is the count of packets received from flow f, and

N_{f}

is the count of packets transmitted to f.

(iii) Average Energy Consumption. The energy consumption is averaged over all nodes in the network.

(iv) The Lifetime Extension. The metric studied is the number of hours of communication achieves when 1 percent, 25 percent, 50 percent, and 100 percent of the nodes die using multipath routing and the shortest path routing.

(v) Energy × Delay. For battery operated sensors, longevity is a major concern and energy efficiency often brings additional latency along with it. Generally, increased energy savings come with a penalty of increased delay. Therefore, there is a tradeoff between energy spent per packet and delay. We capture this with the energy × delay metric and attempt to balance the energy and delay cost for data transmission from sensor networks. Also, energy × delay is an appropriate measure to optimize for in wireless sensor networks. To calculate the energy × delay for these schemes, we multiply the average energy cost to the delay for the given packet sizes.

These measures are intended to provide insight into the ability of the protocols to route packets to their intended destination and the energy efficiency of the protocols in accomplishing that task.

Figure 8 illustrates the latency of the delivery of the packets. As we mention, the benefits in terms of extended lifetime come at the cost of having multipath routing that are longer than the shortest path between a given (sink, source) pair, and Figure 8 illustrates the averaged values of the maximal packet delivery latencies for the approaches considered. As can be seen, both Bezier-based and the shortest routings exhibit lower delivery latencies, nearly 50% smaller than the ones exhibited by sweep and TD, throughout the time in which most of the nodes in the network are still operational. The Bezier-based and the shortest routing exhibit comparable latency performance, since the control points of the outermost Bezier curve have been calibrated to roughly match the “longest-admissible” path used by the shortest path. Sweep, however, exhibits the longest latencies since the protocol does not provide a mechanism to explicitly bound the spread of the alternating routes, and a significant number of routes will tend to spread throughout the entire network deployment area. With the high density of the nodes, fewer nodes in the sweep could transmit simultaneously, resulting in less parallelism. Introducing lossy links also increased latency due to retransmissions caused by bad links. The long duration of the sweep was caused by the current implementation, which did not drop nodes from the neighbor list and forwards down the gradient, resulting in retransmissions on bad links. These implementational issues result in a slow sweep. Moreover, the convergence of the potential function is rather slow and takes $O (N)$ iterations, which slows down the sweep process and increases the latency. An interesting observation is that, toward the end of the simulation time, at which point the network has drastically changed in terms of the available nodes that can be used for routing, the latencies for both Bezier based and k-short approaches tend to increase. Another interesting observation is the behavior of the TD approach: its latency fluctuates frequently, yielding many peaks and valleys in the graph in Figure 8. The mean reason for this phenomenon is that, when switching M vertices (multipath nodes) to T vertices (tree nodes) or switching T vertices (tree nodes) to M vertices (multipath nodes), which are not guaranteed to succeed immediately, hence, the data packets of the given query may need to be temporarily queued. The tree-based approach, rooted at the sink node, is constructed for use in answering queries. Subsequently, each query answer is generated by performing in-network aggregation along the tree, proceeding in a level-by-level fashion from its leaves to its root. However, wireless sensor networks have high communication failure rates (up to 30% loss rate is common), and each dropped message results in an entire subtree of readings being dropped from the aggregate answer, which thereby greatly increases the latency since the packets need to be retransmitted.

Figure 8

The average end-to-end delay.

Another experiment that we conduct is used to measure the packet delivery fraction of the network. Figure 9 shows the degradation of the QoS level at run time, expressed as the percentage of data packets that have been received at the sinks. As one can observe, Bezier-based routing is dropping much fewer packets compared with the other approaches. $TD$ is the worst performing approach, and the main reason for it is that it does not exactly perform alternation among multiple routes for the purpose of load balancing over time. Furthermore, each lost message drops all the packets from an entire subtree. The sweep algorithm has a considerable loss rate because sweep aggregated across the source boundary and then proceeded nicely to the sink boundary and the regular nodes in the middle of the region had a higher probability of collisions because they had more neighbors on average.

Figure 9

The packet delivery fraction.

An important observation that we analyzed through our experiments is the benefits brought by Bezier-based routing in terms of energy cost. Figure 10 depicts the minimum energy depletion rate over the entire network, which, not surprisingly, corresponds to the energy depletion rate of the root nodes. As it can be observed, performing load-balancing by means of represents a better choice than both multipath-Bezier and $TD$ significantly outperforms the shortest path routing and sweep approach. As illustrated in Figure 10, when the routing is performed exclusively along the optimal routes, the network will be declared “dead,” although barely 20% of its total energy was spent. Clearly, both Bezier-based routing and $TD$ have smaller energy consumption than that of the shortest path routing and sweep. This demonstrates that the former can distribute the traffic load more fairly than the latter. This result can be explained by the fact that the traffic of the network is evenly regulated to the different paths while the single path always chooses the geographic-based shortest path, which will unfairly distribute more loads to the nodes along this optimal route than their neighboring nodes. According to this figure, we conclude that the nodes along this shortest path are likely to be overused because these routes have no alternative option. Therefore, the energy of those nodes on this route will drop faster than the other nodes.

Figure 10

The average energy consumption.

Figure 11 illustrates the lifetime extension as function of the percentage of node death. There are six different definitions surveyed in [51], for example, time until the first node dies or time until a certain fraction of the nodes die. We study the number of hours of communication when 1 percent, 25 percent, 50 percent, and 100 percent of the nodes die using the above four schemes. We used the SIDnet-SWANS to evaluate our results and the experiments confirmed that indeed this policy yields the largest lifetime extensions. Data in Figure 11 was obtained by averaging over 10 simulations with 5–10 randomly placed (sink-source) pairs. It illustrates the benefits of alternate routes. As can be seen in Figure 11, the other 3 multipath routings can yield improvements over the shortest path routing in terms of lifetime. To the best of our knowledge, the battery energy of a network node is mainly consumed on forwarding control and data packets. Multipath routing usually increases the energy consumption on the transmission of data messages because some data packets traverse suboptimal paths. On the other hand, it will decrease the energy consumption on the transmission of control messages. This reveals that the Bezier-based multipath routing can achieve the best balanced energy dissipation among the sensor nodes to have full use of the complete sensor network.

Figure 11

The lifetime of the network as function of the percentage of node death.

The lifetime experiment that we conduct is used to measure the energy × delay of the network. The duration of monitoring a continuous query is 20000, 10000, and 2000 packets between the sink and the source for the purpose of minimizing energy × delay while meeting acceptable delays for applications can lead to significant power savings. The sampling interval is 0.1 ms. Figure 12 shows the results for the four schemes based on different packet sizes. As expected, energy × delay increases with the packet size. Figure 12 also shows that as the number of nodes increases, energy × delay becomes greater for all schemes and the Bezier-based routing performs the best.

Figure 12

The energy × delay as function of the number of packets.

The metric of energy × delay is an effect of two factors: the energy consumption and the end-to-end delay for the given packets. The end-to-end delay includes the queue delay in every nodes and the propagation delay from the source to the destination. Multipath routing can reduce the queue delay because the total traffic load is distributed evenly into multiple routes, and therefore, data packets will experience less queuing delay. On the contrary, all the traffic would route along only one path, corresponding to the heavily congested path case. The benefits of multipath routing in reducing queuing delay are more prominent at smaller sampling interval networks where congestion has higher probability to occur and herein, the sampling interval represents the frequency of traffic which is created. With the increase of the sampling interval, the traffic rate created with sampling interval becomes lower and the shortest path routing obtains better end-to-end delay performance than multipath routing. This can be explained by noting that nodes have sufficient time to process and distribute packets in timely manner in the shortest path routing (SPR) at bigger sampling interval while more paths will be handled for multipath routing and thus the queuing delay of the data packets in the source node increases which leads to the increase of the average end-to-end delay. In a word, when the sampling interval reaches some threshold, multipath routing may not be as beneficial in terms of end-to-end delay. With the increase the number of hours of communication, the rate of the energy consumption for the shortest path routing and TD is much faster than the Bezier-based routing and sweep. This is why we observe that the Bezier-based routing and sweep perform better than the SPR and TD when the number of packets is 20000. So we can arrive at a conclusion that increased energy savings come with a penalty of increased delay; however, there surely exists a tradeoff between energy spent per packet and delay.

6. Conclusions and Future Work

We present a novel load-balancing mechanism and Bezier-based multipath routing for wireless sensor networks. The new scheme is simple but very effective to achieve load balancing and congestion alleviation. We have explored an experimental comparison with the shortest path routing, sweep, and Tributaries and Deltas. Our performance study shows the following. (i)

The network traffic can be distributed more evenly onto multipath routing. Load balancing is important to fairly distribute the routing task among the nodes of the network. It can also protect a node from failure considering that a node with heavy duty is likely to deplete its energy quickly.

(ii)

The Bezier-based routing can gain somewhat improvement of the average end-to-end delay at a higher traffic rate.

(iii)

Although it takes much more time for the packet delivery along those multiple paths than the shortest path, the packet delivery fraction of our technique has been improved obviously and the network resource can be utilized efficiently.

Also, we use the Bezier-based multipath routing to balance the energy dissipation to maximize the lifetime of the nodes in a sensor network. However, minimizing energy in isolation has drawbacks because energy efficiency often brings additional latency. Clearly, several practical applications set limits on acceptable latency, as specified by QoS (Quality of Service) requirements. For example, the data transmission delay per packet may have a bound. Beyond this bound, this packet may be dropped. Therefore, our motivation of this paper is to investigate the tradeoff that arises between the end-to-end delay of the data transmission and the lifetime extension of the individual nodes and the network as a whole. We have explored an experimental comparison of the benefits of the Bezier based routing methodology with three different approaches. Our performance study, using several different metrics, has demonstrated that the proposed routing methodology indeed prolongs the lifetime of the network, while maintaining balanced energy levels of the nodes employed and the minimized latency.

However, multipath routing techniques are not without pitfalls. It is worthwhile to mention them clearly, even though they are not captured in our simulation. The primary disadvantages of multipath routing protocols compared to single path protocol are complexity and overhead. We have to consider the overheads that we maintain multiple routes to a destination, which leads to large routing tables at intermediate nodes. Also, we need to take into consideration how to allocate the packets to the multiple routes. Hence, we still need to expand our design to provide the solution to the following problems. Those works will be addressed in the future. (i)

We will provide some insight into choosing the right tradeoff between better performance and increased overheads for multipath routing.

(ii)

How the optimal multipath routing for a given source and sink nodes affects the lifetime gain in a large-scale wireless sensor networks also needs to be investigated.

(iii)

We further will analyse how the number of paths (a factor of K) for a given source and sink nodes affects the lifetime gain and the end-to-end delay in a large-scale wireless sensor networks also needs to be investigated.

Wireless sensor network is and remains a very challenging research field with many problems that are still to be addressed. Our work focused on specific aspects of lifetime extension problems by employing various forms of workload balancing techniques. However, most of our work relies on assumptions that need to be strengthened in order to devise a solution with the same projected performances in a real world deployment. To this end, there is a need to augment our current solutions with new elements of resource-awareness, including the density variations, the mobility, and the sampling interval from the whole nodes. Also, our work analyzed the problem from the perspective of simple queries, point-to-point, and multipoint to point data sampling, aggregation, and routing. It is necessary, however, to place our work in relation to realistic, more complex queries, with a particular interest in range-monitoring queries.

Various solutions have been proposed, in isolation, to distinct problems of interest for sensor networks. Most of the existing approaches in processing, information management, and networking pertaining to sensor networks do not address, in an integrated fashion, the following three major application characteristics that we have considered so far (evolving): data management, query management, and context-awareness routing. Our goal is to devise a methodology of incorporating some of these solutions in a unifying framework in order to realize an efficient, system-wide solution to a group of problems. This is a necessary step in order to automate the control of the sensing devices under complex and unpredictable task requirements and essential for technology transfer to end-users.

Footnotes

Conflict of Interests

The author declares no conflict of interests.

Acknowledgments

The author would like to thank the anonymous reviewers for their insight and suggestions which have substantially improved the content and presentation of this paper. This work was supported by the Fundamental Research Funds for the Central Universities of China under Grant no. 31541311303 and the Research Project Funds (32514113005).

References

Wan

Performance analysis of single-tree and split-tree approach in wireless sensor networks

Proceedings of the International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC ′09)

October 2009

132 135

10.1109/CYBERC.2009.5342196

2-s2.0-72449172855

Wan

K-multipath routing mechanism with load balancing in wireless sensor networks

Proceedings of the 2nd International Symposium Computer Science and Computational Technology (ISCSCT ′09)

December 2009

Huangshan, China

Wan

Multipath routing for continuous query using energy metrics in wireless sensor networks

Proceedings of the 2nd Conference on Power Electronics and Intelligent Transportation System (PEITS ′09)

December 2009

Shenzhen, China

307 310

10.1109/PEITS.2009.5406864

2-s2.0-77749314583

Broch

D. J.

Maltz

Imielinski

Korth

H. F.

Dynamic source routing in ad hoc wireless networks

Mobile Computing 1996 353

Kluwer Academic

153 181

Perkins

C. E.

Royer

E. M.

Ad-hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA ′99)

February 1999

New Orleans, La, USA

90 100

10.1109/MCSA.1999.749281

2-s2.0-34347349933

Mueller

Tsang

R. P.

Ghosal

Multipath routing in mobile Ad Hoc networks: issues and challenges

Performance Tools and Applications to Networked Systems 2004 2965

Berlin, Germany

Springer

209 234 Lecture Notes in Computer Science

Ramanathan

Steenstrup

A survey of routing techniques for mobile communications networks

Mobile Networks and Applications 1996 1 2 89 104

10.1007/BF01193330

2-s2.0-0030261244

Cheng

Niu

Cao

Das

S. K.

QoS aware geographic opportunistic routing in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2013 25 7 1864 1875

10.1109/TPDS.2013.240

Chen

Chamania

Jukan

Drummond

A. C.

da Fonseca

N. L. S.

QoS-constrained multi-path routing for high-end network applications

Proceedings of the IEEE INFOCOM Workshops

April 2009

Rio de Janeiro, Brazil

10.1109/INFCOMW.2009.5072182

2-s2.0-70349696868

10.

Ganjali

Keshavarzian

Load balancing in ad hoc networks: single-path routing vs. multi-path routing

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′04)

March 2004

1120 1125

10.1109/INFCOM.2004.1356998

2-s2.0-8344223699

11.

Nasipuri

Das

S. R.

On-demand multipath routing for mobile ad hoc networks

Proceedings of the 8th International Conference on Computer Communications and Networks

October 1999

Boston, Mass, USA

64 70

10.1109/ICCCN.1999.805497

12.

de Haan

Boucherie

R. J.

van Ommeren

J.-K.

The impact of interference on optimal multi-path routing in ad hoc networks

Managing Traffic Performance in Converged Networks: Proceedings of the 20th International Teletraffic Congress, ITC20 2007, Ottawa, Canada, June 17–21, 2007 2007 4516

Berlin, Germany

Springer

803 815 Lecture Notes in Computer Science

10.1007/978-3-540-72990-7_70

13.

Pham

P. P.

Perreau

Performance analysis of reactive shortest path and multi-path routing mechanism with load balance

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

251 259

2-s2.0-0042976106

14.

Tsilimantos

Gorce

J.-M.

Altman

Stochastic analysis of energy savings with sleep mode in OFDMA wireless networks

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′13)

April 2013

Turin, Italy

1097 1105

10.1109/INFCOM.2013.6566900

2-s2.0-84883082953

15.

Sen

Radunovic

Lee

Kim

K.-H.

CSpy: finding the best quality channel without probing

Proceedings of the 19th Annual International Conference on Mobile Computing & Networking (MobiCom ′13)

September 2013

Miami, Fla, USA

267 278

10.1145/2500423.2500452

16.

Kwon

Shroff

N. B.

Analysis of shortest path routing for large multi-hop wireless networks

IEEE/ACM Transactions on Networking 2009 17 3 857 869

10.1109/TNET.2008.2002222

2-s2.0-67650156001

17.

Nissler

Gotzhein

Performance evaluation of multi-path routing in reservation-based wireless networks

Proceedings of the 12th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWiM ′09)

October 2009

268 273

10.1145/1641804.1641849

2-s2.0-74049102054

18.

Chanak

Samanta

Banerjee

Fault-tolerant multipath routing scheme for energy efficient wireless sensor networks

International Journal of Wireless & Mobile Networks 2013 5 2

19.

Jung

Lee

Yim

Kim

S.-H.

Localized disjoint multipath routing protocol in irregular wireless sensor networks

Proceedings of the 24th IEEE Annual International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC ′13)

September 2013

London, UK

2454 2458

10.1109/PIMRC.2013.6666558

20.

Vasudevan

Adler

Goeckel

Towsley

Efficient algorithms for neighbor discovery in wireless networks

IEEE/ACM Transactions on Networking 2013 21 1 69 83

10.1109/TNET.2012.2189892

2-s2.0-84873998505

21.

Patel

Bansal

Yuan

Murthy

Greenberg

A. G.

Maltz

D. A.

Kern

Kumar

Zikos

Kim

Karri

Ananta: cloud scale load balancing

Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (SIGCOMM ′13)

2013

207 218

10.1145/2486001.2486026

22.

Singh

Woo

Raghavendra

C. S.

Poweraware routing in mobile ad hoc networks

Proceedings of the International Conference on Mobile Computing and Networking

1998

Dallas, Tex, USA

181 190

23.

Chang

J.-H.

Tassiulas

Energy conserving routing in wireless ad-hoc networks

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM ′00)

2000

Tel Aviv, Israel

22 31

10.1109/INFCOM.2000.832170

24.

Chang

J.-H.

Tassiulas

Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks

Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks 2000 1815

Berlin, Germany

Springer

702 713 Lecture Notes in Computer Science

10.1007/3-540-45551-5_59

25.

Intanagonwiwat

Govindan

Estrin

Directed diffusion: a scalable and robust communication paradigm for sensor networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

Boston, Mass, USA

56 67

2-s2.0-0034539015

26.

Song

W.-Z.

Wang

X.-Y.

Frieder

Localized algorithms for energy efficient topology in wireless ad hoc networks

Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′04)

May 2004

Tokyo, Japan

98 108

27.

Aurenhammer

Klein

Voronoi diagrams

Handbook of Computational Geometry 2000

Amsterdam, The Netherlands

North-Holland

201 290

28.

Niculescu

Nath

Trajectory based forwarding and its applications

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ′03)

September 2003

San Diego, Calif, USA

260 272

2-s2.0-1542358974

29.

Val Machado

Goussevskaia

Mini

R. A. F.

Rezende

C. G.

Loureiro

A. A. F.

Mateus

G. R.

Nogueira

J. M. S.

Data Dissemination Using the Energy Map 2005

St. Moritz, Switzerland

WONS

30.

Zhu

Setia

Jajodia

Geographic and energy-aware routing in sensor networks

Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP ′03)

November 2003

Atlanta, Ga, USA

31.

Karp

Kung

H. T.

GPSR: greedy perimeter stateless Routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

New York, NY, USA

ACM

243 254

2-s2.0-0034547115

32.

Madden

Franklin

M. J.

Hellerstein

J. M.

Hong

Tag: a tiny aggregation service for ad hoc sensor networks

Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI ′02)

December 2002

Boston, Mass, USA

33.

Nath

Gibbons

P. B.

Seshan

Anderson

Synopsis diffusion for robust aggregation in sensor networks

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04) 2004 250 262

10.1145/1031495.1031525

34.

Manjhi

Nath

Gibbons

P. B.

Tributaries and deltas: efficient and robust aggregation in sensor network streams

Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD ′05)

2005

287 298

35.

Fan

K.-W.

Liu

Sinha

Structure-free data aggregation in sensor networks

IEEE Transactions on Mobile Computing 2007 6 8 929 942

10.1109/TMC.2007.1011

2-s2.0-34347219150

36.

Skraba

Fang

Nguyen

Guibas

Sweeps over wireless sensor networks

Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN ′06)

April 2006

Nashville, Tenn, USA

143 151

10.1145/1127777.1127802

2-s2.0-34247374834

37.

Shrivastava

Buragohain

Agrawal

Suri

Medians and beyond: new aggregation techniques for sensor networks

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04)

November 2004

New York, NY, USA

ACM

239 249

2-s2.0-27644511275

38.

Farin

G. E.

Hoschek

Kim

M.-S.

Handbook of Computer Aided Geometric Design 2002

New York, NY, USA

Elsevier

39.

Pham

P. P.

Perreau

Increasing the network performance using multi-path routing mechanism with load balance

Ad Hoc Networks 2004 2 4 433 459

10.1016/j.adhoc.2003.09.003

2-s2.0-5444227761

40.

Harms

Multipath routing for mobile ad hoc networks

Journal of Communications and Networks 2002 4 1 48 58

2-s2.0-0040077824

41.

Krishnamurthy

S. V.

Tripathi

S. K.

A framework for reliable routing in mobile ad hoc networks

Proceedings of the IEEE INFOCOM

March 2003

San Francisco, Calif, USA

42.

Nasipuri

Castañeda

Das

S. R.

Performance of multipath routing for on-demand protocols in mobile Ad Hoc networks

Mobile Networks and Applications 2001 6 4 339 349

10.1023/A:1011426611520

2-s2.0-0035425905

43.

Banner

Orda

Multipath routing algorithms for congestion minimization

IEEE/ACM Transactions on Networking 2007 15 2 413 424

10.1109/TNET.2007.892850

2-s2.0-34247279630

44.

Hyytiä

Virtamo

On optimality of single-path routes in massively dense wireless multi-hop networks

Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWiM ′07)

October 2007

Chania, Greece

ACM

28 35

10.1145/1298126.1298135

2-s2.0-42149120735

45.

Lou

Liu

Zhang

Cheng

D.-Z.

Performance optimization using multipath routing in mobile ad hoc and wireless sensor networks

Combinatorial Optimization in Communication Networks 2006 18

New York, NY, USA

Springer

117 146 Combinatorial Optimization

10.1007/0-387-29026-5_5

MR2249050

46.

Nagpal

Shrobe

H. E.

Bachrach

Organizing a global coordinate system from local information on an ad hoc sensor network

Proceedings of the Information Processing in Sensor Networks (IPSN ′03)

2003

Palo Alto, Calif, USA

333 348

47.

Fang

Ning

A beacon-less location discovery scheme for wireless sensor networks

Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

161 171

10.1109/INFCOM.2005.1497888

48.

Reichenbach

Born

Timmermann

Bill

A distributed linear least squares method for precise localization with low complexity in wireless sensor networks

Proceedings of the 2nd IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS ′06)

2006

San Francisco, Calif, USA

514 528

10.1007/11776178_31

49.

Bulusu

Estrin

Girod

Heidemann

Scalable coordination for wireless sensor networks: self-configuring localization systems

Proceedings of the 6th International Symposium on Communication Theory and Applications (ISCTA ′01)

July 2001

Toronto, Ontario, Canada

50.

Gao

Zhang

Load-balanced short-path routing in wireless networks

IEEE Transactions on Parallel and Distributed Systems 2006 17 4 377 388

10.1109/TPDS.2006.49

2-s2.0-33644896203

51.

Dong

Maximizing system lifetime in wireless sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN ′05)

2005

13 19

Energy-Efficient Adaptive Routing and Context-Aware Lifetime Maximization in Wireless Sensor Networks

Abstract

1. Introduction

1.1. Motivational Scenario

2. Related Work

3. Query Model and Problem Formulation

3.1. Query Model

3.2. Setting

3.3. Problem Formulation

3.4. Goals

4. Bezier-Based Multipath Routing Algorithm

4.1. Route Establishment

Algorithm 1: Construction Bezier curve routes.

4.2. The Analysis of Finding Multiple Node-Disjoint Paths

4.3. Data Transmission

4.4. Impact of k

5. Performance Evaluation of the Bezier-Based Multipath Routing

6. Conclusions and Future Work

Footnotes

Conflict of Interests

Acknowledgments

References