Location-based reliability differentiated service for wireless sensor networks

Abstract

Designing reliability differentiated services for missions with different reliability requirements has become a hot topic in wireless sensor networks. Combined with a location-based routing mechanism, a quantified model without full network topology is proposed to evaluate reliability. By introducing a virtual reference point, the data transfer is limited in a specified area. The reliability function of the area is given. A detailed analysis shows that the function increases quadratically with the distance between the source node and the reference node. A reliability differentiated service mechanism is then proposed. The simulation results show the efficiency of the proposed mechanism.

Keywords

wireless sensor networks / reliability / service-differentiated / location-based routing mechanism

Introduction

Wireless sensor networks (WSNs) have wide applications in battlefields and emergency response. WSNs need improved transfer reliability against package loss rate caused by node and link failures [1-3]. Supplying a uniform service for missions with different reliability requirements should be forbidden to reduce energy consumption. Traditional routing schemes are based on end-to-end path discovery, resource reservation and path recovery along the discovered path, which is not suitable for WSNs because of unavoidable path discovery latency and resource reservation. Therefore, recent research has focused on route mechanism without a prior path set-up and global topology information [4-15], which is termed the stateless routing algorithm. However, stateless routing will bring exponential packets forward because of its flooding-like mechanism, especially for high density WSNs. Thus, designing an energy efficient approach without a global network state and path discovery has attracted much attention.

This article proposes a novel scheme that introduces a virtual reference node with the help of triangle inequality to restrict data relay in a specified area. The proposed algorithm efficiently reduces energy consumption and provides a reliability differentiated service in a localized way.

Related work

Stateless routing schemes have the same requirements [4-15]. Each sensor knows its nodes’ and sink node’s positions, otherwise data reporting will lose guidance. For example, workers can go to rescue in battlefields or other emergent circumstances with the help of position information. Thus, the global positional system (GPS) [4] is introduced in WSNs to solve the localization problem. However, due to cost factors, it is highly undesirable to have a GPS receiver in each sensor node. Fortunately, there are efficient distributed GPS provision service algorithms [5,6]. As a result, location-based routing protocols have been widely studied. Because such routing protocols will forward packets through direct neighbors, they can avoid path discovery, reservation and recovery. Many stateless routing protocols [7,8] are proposed based on location techniques.

GPSR [7] is an efficient routing technique without priori path set-up that uses the greedy forwarding geographic routing approach, which is the first approach introducing location-based technique. However, packets always reach a local maximum, and therefore the recovery overhead is significant. They still cannot support service differentiation. Many improvements on GPSR have been developed [8-11]. Path redundancy and reliability are leveraged in ReInForM [10] for desired reliability using local information. MMSPEED [11] extends it in differentiating services in both timeliness and reliability domains, and proposes a dynamic approach to compensate for inaccuracies of local decisions. However, the overheads incurred by probability flooding-like routing in the above work are energy-wasting. This article will show that restricted data transfer can reduce those overheads.

There are four well-known restricted data transfer protocols [12-15], among which Gossip [12] is the first for Ad-hoc networks and is revised for WSNs. However, it has poor scalability. DREAM [13] improves Gossip by forecasting an expected region containing destination node D (a circle C), and calculating two tangents, line1 and line2, between source nodes S and C. The data transfer is restricted in a taper-like region surrounded by line1, line2 and C. Similar to DREAM, LAR [14] also estimates an expected region C of destination and then computes a random rectangle region containing C to transfer data. DREAM and LAR are quite suitable for Ad-hoc networks. TBF [15] proposes a trajectory-based forwarding scheme and extends restricted data transfer technique to WSN applications. The trajectory is set by the source and the forwarding decision is based on its relationship with the trajectory rather than names of intermediate nodes. Data transfer is restricted in a region around the trajectory. In the three protocols (DREAM [13], LAR [14] and TBF [15]), the nodes forward data in the expected region using a greedy algorithm to find routes.

However, they may fail to find a path between source and destination, because the path may exist outside the calculated region as a result of the greedy algorithm. This is termed ‘void’ problem and the solution is the right hand technique [7]. Unfortunately, it should be avoided to reduce overheads. Furthermore, there are no theoretical rules for calculating a restricted transfer region. The following sections will show some candidate rules by introducing triangle inequality.

Network model and problem

Network model

All the sensors are randomly distributed in a plane M, and that

1) A sensor i can and only can receive messages sent by other sensors located in the circle of radius r centered at i.

2) The radius R of M is much bigger than r.

3) Sensors do not move after the distribution.

4) Each sensor has its own location information by GPS or other location techniques.

5) Different operations have different reliability requirements.

6) Stateless routing protocols are discussed in this article.

In the above properties, 1) -3) have been widely used in WSN researches [1-15]. Property 4) can be implemented by distributed location techniques [4-7]. Properties 5) and 6) are the same preconditions of reliability differentiated service researches in WSNs [8-15].

Problem

Let source node S send data to a destination node D. The Cartesian coordinates of S and D are S(S_x,S_y) and D(D_x,D_y), respectively. Let the reliability requirement of this mission be P^{\mathrm{r}\mathrm{e}\mathrm{q}}. Each sensor maintains its direct neighbors’ information, including location and average lost radio package.

The problem is how to select the right route that satisfies the reliability requirement by only using local information with the least possible energy consumption.

Scheme

Relay in specified area

Suppose source node S and destination node D cannot communicate directly. Packets are transmitted multihop through the other sensor nodes in the WSN. Suppose that P is a node at the route from S to D. Now we consider the possible area containing relay nodes with the help of triangle inequality.

First, the relay nodes at the route from P to D (route PD for simplicity) are considered. If route PD is a beeline, then all the relay nodes should be in the beeline PD. Otherwise, the transmission distance from P to D among relay nodes is at least |PD| according to triangle inequality. For example, suppose the packets are transmitted from node P to node E, and then to node D. Obviously, the transmission distance is \left|PE\right|+\left|ED\right|\ge \left|PD\right|. Hence, we have:

Rule 1 The relay nodes at the route PD should be in the circular region C₁ of radius at least |PD| centered at P.

Similar to Rule 1, we can obtain that relay nodes at the route SP should be in the circular region C₂ of radius at least |SP| centered at P. Without loss of generality, if \left|PS\right|\ge \left|PD\right|, then C₁ is inside C₂. Rule 2 is then obtained.

Rule 2 Relay nodes should be in the circular region C₂ of radius at least |SP| centered at P. The nodes outside C₂ can be considered as redundant nodes. Figure 1(a) shows the scenario.

Second, we consider the one hop scenario as shown in Fig. 1(b). The data transmission distance from S to D relayed by P is |SP|+|PD|. Similar to the analysis of Rule 1 and Rule 2, it is easy to know that the transmission distance from S to D among relay nodes is at least |SP|+|PD|. Then we have:

Rule 3 Relay nodes should be in the circular region C₃ of radius at least |SP|+|PD| centered at S. The nodes outside C₃ can be considered as redundant nodes, as shown in Fig. 1(b).

Obviously, circle C₂ and C₃ will overlap, as shown by the shadow area C₄ in Fig. 1(c). This indicates that relay nodes in the route SD should be in the area C₄. According to Rule 2 and Rule 3, we summarize the following equation to determine the relay nodes from source node S to destination D:

(1)\begin{array}{l}\left|AP\right|\le \max \{\left|PS\right|,\left|PD\right|\},\\ |\left|AS\right|\le \left|PS\right|+\left|PD\right|.\end{array}

For any node A, if Eq. (1) is satisfied, it becomes a relay candidate node.

The data transfer is then limited in the specified area C₄. For any node A, at least two times and at most four times Euclid distance calculation are required to determine whether A should relay data. The energy consumption of these simple calculations is much lower than that of data transmission. As a result, the overhead is significantly reduced.

Rule 4 Relay nodes should be in the overlapped region C₄. The nodes outside C₄ can be considered as redundant nodes, as shown in Fig. 1(c).

The data transfer is then restricted in the specified area C₄ located by S, D and P.

Note that C₄ should cover the radio range of destination; otherwise the path may not exist. Let the distance between P and S be x, the distance between S and D be b and the radio range be r. Then it can be seen that when the radius of C₃ is larger than (b+r), C₄ can cover all the nodes in the radio range of destination, as illustrated in Fig. 1(d). According to Rule 3, if the radius of C₃ is at least |SP|+|PD|, then we have |SP|+|PD|>b+r. Note that |PD|=|SP|-|SD|. Thus we have Rule 5.

Rule 5 Let x be the distance between P and S. Let b be the distance between S and D. Let r be the radio range. Then x should satisfy

(2)x>b+\mathrm{0.5}r.

How to locate P

Notice that the longer the distance between P and beeline SD, the larger the area between P and SD covered by C₄. Especially, if P is above SD, then C₄ will cover more sensor nodes above SD than below SD. Thus, the more relay nodes may be above SD. However, relay nodes should have the same distribution on both sides (above and below) of SD without global network topology information. Otherwise the overload balance will be broken. As a result, we have

Rule 6P should be on line SD, as shown in Fig. 1(d).

Notice that the whole topology of WSN is unknown. Therefore, we can conclude the following under the assumption that nodes S and D are connected in the WSN. The larger the area of C₄, the more sensor nodes will participate in data relay. As a result, the higher the successful transfer probability. Since the area of C₄ is determined by the position of nodes S, D and P, while nodes S and D are always known, then the area of C₄ will be determined by the position of node P. By denoting the area of C₄ as S_{C_{\mathrm{4}}}, S_{C_{\mathrm{4}}} can be expressed using the positions of nodes S, D and P, as shown in Proposition 1.

Proposition 1 Given source node S, destination node D, and reference point P. Let the distance between P and S be x, and that of S and D be b. The data transfer in the WSN follows Rule 1–Rule 6. Then S_{C_{\mathrm{4}}} is given by the following equation and increases strictly with x:

(3)

Proof Suppose S(0,0), D(b,0) and P(x,0). According to Eq. (1), x\ge b/\mathrm{2}. Let the polar coordinates of any node M in circulars C₂ and C₃ be M(ρ,θ), then we have the equation:

For x\ge b, let the circulars C₂ and C₃ intersect at nodes E(2x,β) and F(\mathrm{2}x,\mathrm{2}\mathrm{\pi }-\beta ), where \cos \beta =(\mathrm{2}x-b)/\mathrm{2}x, and OP intersect with EF and C₃ at H and G respectively, as shown in Fig. 2. Then P\in (O,H]orP\in (H,G).

For P\in (O,H], where (\mathrm{2}x-b)\cos \beta >x, as shown in Fig. 2(a). Denote the area of C₄ as S_{\mathrm{1}a}, then

$$\begin{gathered} S_{\mathrm{1}a}=\mathrm{2}(S_{\mathrm{E}\mathrm{P}\mathrm{O}}+S_{\mathrm{E}\mathrm{P}\mathrm{G}})=\mathrm{2}(S_{\mathrm{E}\mathrm{P}\mathrm{O}}+S_{\mathrm{E}\mathrm{O}\mathrm{G}}-S_{\mathrm{E}\mathrm{O}\mathrm{H}}+S_{\mathrm{E}\mathrm{P}\mathrm{H}}) \\ =\mathrm{2}({\displaystyle {\int }_{\beta }^{\frac{\mathrm{\pi }}{\mathrm{2}}}{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{x}^{\mathrm{2}}\mathrm{d}\theta }+{\displaystyle {\int }_{\mathrm{0}}^{\beta }{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{(\mathrm{2}x-b)}^{\mathrm{2}}\mathrm{d}\theta -{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{(\mathrm{2}x-b)}^{\mathrm{2}}\sin \beta \cos \beta +{\displaystyle \frac{\mathrm{1}}{\mathrm{2}}}{x}^{\mathrm{2}}\sin (\mathrm{2}\beta )\cos (\mathrm{2}\beta )}) \\ =\mathrm{\pi }{x}^{\mathrm{2}}+(\mathrm{2}{x}^{\mathrm{2}}-\mathrm{4}bx+b^{\mathrm{2}})\arccos {\displaystyle \frac{\mathrm{2}x-b}{\mathrm{2}x}}+{\displaystyle \frac{\mathrm{1}}{\mathrm{4}{x}^{\mathrm{2}}}}(x+b)(\mathrm{6}bx-\mathrm{5}{x}^{\mathrm{2}})\sqrt{\mathrm{3}{x}^{\mathrm{2}}-\mathrm{2}bx-b^{\mathrm{2}}},x\ge b. \end{gathered}$$

For P\in (H,G), where , as shown in Fig. 2(b). Denote the area of C₄ as S_1b. According to the symmetry property, S_{\mathrm{1}a}=S_{\mathrm{1}b}.

Similarly, when , we can get the area of C₄.

Then the area of C₄ (denoted as S_{C_{\mathrm{4}}}) is shown by S_1a and S₂.

Given the source and destination nodes, then b is a constant. Thus, S_{C_{\mathrm{4}}} varies with undependable variable x and is continuous. Differentiating S_1a and S₂ about x, we obtain that the derivative of S_1a and S₂ is greater than zero. Notice that S_{\mathrm{2}}(b/\mathrm{2})=\mathrm{\pi }{b}^{\mathrm{2}}/\mathrm{4}>\mathrm{0}. As a result, S_{C_{\mathrm{4}}} increases strictly with x.

To summarize, we have Proposition 1.

Corollary 1S_{C_{\mathrm{4}}} increases quadratically with x.

Sketch According to Eq. (3), it is easy to obtain

So S_{C_{\mathrm{4}}}=O(x^{\mathrm{2}}). According to Proposition 1, S_{C_{\mathrm{4}}} increases quadratically with x.

The above analysis demonstrates that the area of C₄ increases quadratically with x, and that the number of sensor nodes participating in data relay also increases quadratically. As a result, the probability of forwarding failure will decrease quadratically. However, the energy consumption will increase quadratically. Obviously, x should not be too large. Otherwise the proposed data transfer mechanism in a specified area will not be worth doing because of the additional transfer (the location of reference node P).

Suppose that R is the network radius, δ is the node density, and E is the energy consumption of packet with L bytes for each sensor node. Note that E is in direct ratio to L. Then the total energy cost in MMSPEED can be expressed as \mathrm{\pi }{R}^{\mathrm{2}}\delta L. Since our proposal needs an additional transfer of reference node location information with two bytes, then the total energy is about S_{C_{\mathrm{4}}}\delta (L+\mathrm{2}). The source node can then calculate S_{C_{\mathrm{4}}}\delta (L+\mathrm{2}) and \mathrm{\pi }{R}^{\mathrm{2}}\delta Lto determine whether C₄ should be specified. If , then specified transmission should be performed, otherwise no operation is done. If c=L/(L+\mathrm{2}), then . According to Proposition 1, it can be known that S_{C_{\mathrm{4}}}-\mathrm{\pi }{x}^{\mathrm{2}} also increases with x. Hence, it can be relaxed to . We then have Rule 7.

Rule 7 Let x be the distance between P and S, b the distance between S and D, and r the radio range. Then x should satisfy

(4)

To summarize, the source node should select P in line SD. The longer |SP| (x) is, the smaller the probability of forwarding failure, and the more energy will be consumed. P should satisfy

(5)

Reliability differentiation

Let the required reaching probability be P^{\mathrm{r}\mathrm{e}\mathrm{q}}. Here we follow the reliability evaluation methods [3,4] without the whole topology. Let all the sets of direct neighbors of node i be K. Each node i maintains the recent average of packet loss percentage e_{i,j} to each direct neighbor j. Node i can then locally estimate the reachability from node i to node d via neighbor j as follows:

(6)R{P}_{i,j}^d=(\mathrm{1}-e_{i,j}){(\mathrm{1}-e_{i,j})}^{\left|\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_{j,d}/\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_{i,j}+\mathrm{1}\right|},

where \left|{dist}_{j,d}/{dist}_{i,j}+\mathrm{1}\right| is the local hop count estimation from j to the final destination d.

Now i will select one neighbor j and assign P_j^{\mathrm{r}\mathrm{e}\mathrm{q}}=R{P}_{i,j}^d to it. i then adds j to its forwarding list J one by one until that TR{P}_{i,J}^d value just equals P^{\mathrm{r}\mathrm{e}\mathrm{q}}, where TR{P}_{i,J}^d is defined as

(7)TR{P}_{i,J}^d=\mathrm{1}-{\displaystyle \prod _{j\in J}(\mathrm{1}-P_j^{req})}.

If the TR{P}_{i,J}^d value just exceeds P^{\mathrm{r}\mathrm{e}\mathrm{q}}, then i randomly selects a node j from J and relaxes the assignment one by one until TR{P}_{i,J}^d=P^{\mathrm{r}\mathrm{e}\mathrm{q}}.

Proposed approach

1) S randomly selects P satisfying Eq. (5), then attaches P^{\mathrm{r}\mathrm{e}\mathrm{q}} and P(P_x,P_y) to packets; if Eq. (5) cannot be satisfied, then S attaches only P^{\mathrm{r}\mathrm{e}\mathrm{q}} to packets.

2) For any node A receiving the message, if P(P_x,P_y) is attached, then restricted data forwarding starts up; and if Eq. (1) is satisfied, A becomes a relay node and goes to step 3); if Eq. (1) is not satisfied, A does not receive the packet; if P(P_x,P_y) is not attached, then A forwards packets as follows.

3) For each relay node, it selects forwarding paths TR{P}_{i,J}^d>P^{req}, where TR{P}_{i,J}^d is given by Eq. (7).

Comparisons

Simulation environment

We simulate our proposal using a GLOMOSIM simulator [16] in a personal computer with 2.99 GHz CPU and 512 MB RAM. Because the protocol MMSPEED [11] can provide reliability differentiated services in a localized way for WSNs in the literature, and can be improved using restricted data transfer, we use TBF [15] and GPSR [7] to extend MMSPEED. Their performances on efficiency and overheads (void occurring and energy consumption) are compared with TBF. The general simulation environment is mainly drawn from Ref. [4] for fair comparison and summarized in Table 1.

Efficiency

To show the efficiency by introducing restricted area transfer technique, TBF extends MMSPEED (TBF-MM), GPSR extends MMSPEED (GPSR-MM) and the proposed scheme are compared. The required and obtained reliabilities (proposed scheme) are listed in Fig. 3, while the number of void problems occurring is shown in Table 2.

Figure 3 shows the efficiency of the proposed scheme under different node densities when R=100, and n varies from 200 to 600 with increments of 200. The x-line shows the reliability requirements, while the y-line shows the obtained reachabilities. Figure 3 indicates that the proposed scheme can efficiently provide reliability differentiated services.

Table 2 shows the average results in a network with different node densities for GPSR extend MMSPEED (GPSR-MM), TBF-MM and the proposed scheme. The comparison shows that the proposed scheme can efficiently reduce the number of void problems occurring, which answers the analysis in Sect. 4.

Energy consumption and scalability

The energy consumption comparison of the proposed scheme, TBF, and MMSPEED is shown in Fig. 4. The simulations are run under R=100 and n=100. The sink node is located in the center of the terrain. Each protocol will independently run 1000 times. Each time a random source node will send one payload to the sink node. Figure 4 shows that the proposed scheme has better performance than the other two.

From the efficiency and energy consumption comparison, it can be seen that TBF has also good scalability under different network sizes and node densities.

Conclusions

Reliability differentiated services with local information, also termed stateless reliability differentiated routing, has become a hot topic in WSNs. Location-based protocol can provide good support for them without global information. Many interesting related researches have been proposed, which, however, mostly fail on either unignorable overheads or theoretical supports.

This article shows a localized energy efficient algorithm for reliability differentiated services in WSNs. The analysis and simulations show that the proposed scheme has the following advantages:

1) Sensors can dynamically select forwarding nodes by only using local information except the sink node’s position.

2) When providing reliability differentiated services, the overhead can be reduced by introducing restricted data forwarding techniques.

3) Rules 1-7 show where the virtual location point P should be, and the upper and lower bounds of the distance between P and source node, i.e., the theoretical supports for selecting restricted regions.

4) The proposed scheme has good scalability and thus is more suitable for large scale WSNs.

The Rules 1-6 proposed are also suitable for other QoS in WSNs. For Rule 7, the upper bound should be modified according to different QoS requirements, which shall be our future research direction.

References

[1] Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communications Magazine, 2002, 40(8): 102-114

[2] Estrin D, Govindan R, Heidemann J, Kumar S. Next century challenges: scalable coordination in sensor networks. In: Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Seattle, USA. ACM press, 1999, 263-270

[3] Wang, L M, Ma J F, Wang C. Degree of fault-tolerance and intrusion-tolerance for topologies of wireless sensor networks. Acta Electronica Sinica, 2006, 34(8): 1446-1451

[4] Hofmann-Wellenhof B, Lichtenegger H, Collins J. Global Positioning System: Theory and Practice. 4th ed. Austria: Springer–Verlag/Wien, 1997

[5] Bulusu N, Heidemann J, Estrin D. GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications, 2000, 7(5): 28-34

[6] Hightower J, Borriello G. Location systems for ubiquitous computing. Computer, 2001, 34(8): 57-66

[7] Karp B, Kung H T. GPSR: Greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Boston, USA. ACM Press, 2000, 243-254

[8] He T, Stankovic J A, Lu C, Abdelzaher T. SPEED: a stateless protocol for real-time communication in sensor networks. In: Proceedings of the 23rd International Conference on Distributed Computing Systems. Rhode Island: IEEE Computer Society, 2003, 46-55

[9] Bhatnagar S, Deb B, Nath B. Service differentiation in sensor networks. In: Proceedings of the Fourth International Symposium on Wireless Personal Multimedia Communications, 2001

[10] Deb B, Bhatnagar S, Nath B. ReInForM: reliable information forwarding using multiple paths in sensor networks. In: Proceedings of the 28th Annual IEEE Inteernational Conference on Local Computer Networks, 2003, 406-415

[11] Felemban E, Lee C G, Ekici E. MMSPEED: multipath Multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks. IEEE Transactions on Mobile Computing, 2006, 5(6): 738-754

[12] Haas Z J, Halpern J Y, Li L. Gossip-based Ad hoc routing. In: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002). New York: IEEE Communications Society, 2002, 3: 1707-1716

[13] Basagni S, Chlamatac I, Syrotiuk V RWoodwardB A, . A distance routing effect algorithm for mobility (DREAM). In: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, USA. ACM Press, 1998, 76-84

[14] Ko Y B, Vaidya N H. Location-aided routing (LAR) in mobile Ad hoc networks. In: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, USA. ACM Press, 1998, 66-75

[15] Niculescu D, Nath B. Trajectory based forwarding and its applications. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, USA. ACM press, 2003, 260-272

[16] Warneke B, Last M, Liebowitz B, Pister K S J. Smart dust: communicating with a cubic-millimeter computer. Computer, 2001, 34(1): 44-51

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg