Towards Efficient and Secure Geographic Routing Protocol for Hostile Wireless Sensor Networks

Abstract

Traditional routing protocols are quite vulnerable under the attacks from both external and internal attackers. In this work, we examine the impact of a wide variety of attacks in malicious wireless sensor networks scenario. An Efficient and Secure Geographic Routing protocol ESGR is proposed to exploit the geographic location, cryptography mechanisms, and broadcast nature of the wireless channel. ESGR utilizes the geographic leashes and the TESLA scheme to provide resistance against the Sybil attack and wormhole attack. Meanwhile, it employs a distributed trust model and the packets opportunistic forwarding to prevent black hole and gray hole attacks. We demonstrate the results through analysis and simulations that ESGR effectively mitigates a specific variety of attacks and ensures high packet delivery rate in malicious sensor network environment.

1. Introduction

Wireless sensor networks (WSNs) have become an attractive solution for environment monitoring, target tracking, and battlefield surveillance applications nowadays. The wireless network routing protocols that majorly address the time-varying topology can be roughly divided into three categories: flat routing, hierarchical routing, and geographic routing. The flat routing includes table-driven routing and on-demand routing, such as DSDV [1], DSR [2], and AODV [3]. The hierarchical routing, for example ZRP [4], provides scalable management to multiple network levels. Geographic routing, such as GPSR [5], is designed for the networks provided with specific positioning information, such as GPS (Global Positioning System) or other location determination techniques [6]. Based on the information, each node in the GR only keeps the local one-hop connectivity and makes the forwarding decision on the fly. As it does not use control packets to establish a path, the geographic routing is more resilient compared with other types of routings.

In the adversarial environments, attacks come from both the external and internal attackers. The external attackers who do not possess the credentials to participate could be excluded by the authentication mechanisms. However, due to the constrained resource, such as the network bandwidth, the processing capability, and the battery capacity of the sensor node, traditional asymmetric cryptography mechanisms cannot be directly deployed over the WSNs. For example, some Public Key Infrastructure inappropriate for the length of the ciphertext has led to costly transmission or storage. Other than the external attacks, a typical internal attack would compromise a node to gain access to the secret keys stored on it. The asymmetric cryptography mechanisms are not the practicable countermeasures against such attacks [7, 8]. In this paper, we study a variety of attacks against geographic routing in wireless sensor networks and propose a novel attack detection and defense algorithm. It would leverage the geographic locations of nodes, the efficient cryptography mechanisms, and the broadcast nature of wireless channel.

The location in GR is the key information in the geographic routing. An attacker or the compromised node could falsify its location to get more chances to disrupt the routing service if there is not a proper method to verify its claimed location. Unfortunately, most of the proposed secure routings do not deal with it. Only a few of prior works [9, 10] have suggested to use the secure anchor nodes to verify the location. However, these anchors composing a basic infrastructure are required to be trustful and communicate securely among each other. Unlike previous solutions, we consider the issue in the design of the protocol without the extra cost of setting up and maintaining such a secure infrastructure. Our work verifies a sensor node's position by geographic leashes [11] combined with TESLA scheme [12] to detect attacks associated with location, such as the Sybil attack and wormhole attack.

Based on the verification results of location, we present an Efficient and Secure Geographic Routing protocol (ESGR) for WSNs. To further resist other routing attacks such as black hole or gray hole attack, the basic idea of ESGR is an opportunistic routing [13–15]. In addition, it adopts a novel trust model leading to an effective metric against a range of attacks from the external to internal attacks in hostile sensor networks. Provided by the routing metric in ESGR, more receivers would be opportunistically selected as the next hop candidates to forward the packet, and the transmission would not be interrupted as long as there are still candidates to choose from. Therefore, ESGR's per-hop packet transmission is controlled and observed by the sender instantly. Our simulation results show that ESGR enables more than 95% packet delivery rate (PDR) when one fifth of nodes become black hole nodes. Even when one half of sensor nodes drop packets, its PDR can still maintain more than 85%.

We summarize the main advantages of ESGR as follows.

First, it is based on the geographic forwarding with small per-node local state, which means there are no routing tables to maintain, so the forwarding decisions are made on the fly. State locality with minimal overhead is crucial to ESGR's efficiency.

Second, the detection of the malicious behavior is based on the broadcast nature of the wireless channel. Nodes verify the locations of their neighbors by both the geographic leashes and TESLA mechanisms. To reduce the latency that is brought about by TESLA, ESGR predicts its energy consumption to enable instant authentication.

Third, the opportunistic approach can provide a certain degree of redundancy and randomness to enhance the resiliency in face of malicious nodes’ misbehaviors. In order to prevent packet loss, more nodes are selected to be the forwarding candidates. If one of candidates drops the packet, ESGR can select another one from the candidates until the packet is successfully transmitted.

Fourth, the direct trusted information based on watching the next hop's forwarding is used as ESGR's primary trust metric. A sensor node that relays traffic data will earn higher trust from the neighbor nodes. With every node estimating and acting on trust metrics, it is able to route around unreliable neighbors.

Finally, ESGR is shown to be secure and efficient through theoretical analysis and extensive simulations. It achieves 1.5 times higher PDR than the other two protocols and is scalable with an acceptable overhead.

The rest of the paper is organized as follows. The related work is in Section 2. We describe the network and security model in Section 3. Section 4 presents our protocol ESGR. The security and efficiency analysis is performed in Section 5. Section 6 provides experimental results that demonstrate the effectiveness of ESGR in addressing the considered attacks. We conclude our paper in Section 7.

2. Related Work

There are several secure flat routing schemes in the prior works, secure table-driven routing schemes, and secure on-demand routing schemes (such as, [16–18]). SEAD [16] protects distance-vector calculations from distance decreasing and uses hash chains to authenticate routing updates, which tends to have high communication overhead. As a result, it would not be suitable in the large-scale sensor networks. In [17], the authors propose an on-demand routing protocol ODSBR, which uses an adaptive probing technique to detect the malicious link caused by individual or collusion nodes. In [18], they present an algorithm detecting the Byzantine attacks during route discovery and then propose an on-demand routing whose metric combines a node's trustworthiness and performance. However, as a predetermined route must be established before a packet transmission, it introduces control messages for both table-driven and on-demand routings. They would become the attackers’ major targets leading to vulnerability of the sensor networks.

To secure geographic routing, the authors in [19] propose a secure forwarding mechanism providing the authentication and integrity by the TIK protocol. It also combines with a secure grid location service to verify the location information. However, the protocol requires an assumption that all nodes are tightly time synchronized. In our work, we only require loosely synchronized clocks with an upper bound on the sending time [20]. SBGR [21] is a beaconless geographic routing where the nodes compete in a distributed way to acquire the chance to forward the packets. SIGF [22] presents a configurable secure geographic routing family for the wireless sensor networks and makes the tradeoff between security and performance. Neither of them responds to the attacks associated with their locations. In [9], the authors combine lightweight localization techniques with intrusion identification techniques for accurate location information. Their routing protocol then incorporates a distributed trust model to prevent some routing attacks. Liu et al. [10] deploy a location verification algorithm to address the attacks falsifying the location information and then propose a trust-based multipath routing. These works [9, 10] have some similarities with ours, but their location verification schemes rely on a large number of secure anchors to cover all the sensor nodes. Our protocol does not require such an infrastructure and makes use of the geographic leashes and TESLA scheme to defend against these location relevant attacks.

Geographic routing or position-based routing, such as GPSR, has drawn much attention in the literature for its simplicity and efficiency [23–28]. However, this scheme alone does not guarantee delivery due to the existence of local minima (or dead ends) [5]. To tackle the issue, [25, 26] assign for each node a virtual coordinate in a new plane and perform greedy forwarding based on the virtual coordinates. The authors in [28] decompose a given network into a minimum number of greedily routable components, where greedy routing is guaranteed to work. In this paper, we do not discuss the extension since the increasing complexity does not add much in our work.

3. Network and Security Model

3.1. Network Model

We consider a wireless sensor network which consists of sinks and large number of sensor nodes randomly deployed in the network. Sinks are considered to be always trusted, and sensor nodes may be compromised by the adversary. Nodes participate in the data forwarding for other nodes. We assume that the wireless channel is symmetric. All the nodes can communicate with each other within the transmission range R. Each node is stationary in its location and sometimes turns off the transceiver for reducing energy consumption.

The locations of sinks as important resources are known in advance in the system. For the reason of geographic routing, all the sensors first need to obtain their own positions. We assume that each node's position is securely decided once it is deployed in the network. Moreover, all the nodes in the network are loosely time synchronized. Nodes can overhear and then verify the transmissions in their one-hop neighbors over wireless channel, which enables detection of malicious behaviors.

ESGR requires that, for each pair of end nodes, a source s and a sink d that wish to communicate securely across the network share a preestablished symmetric key. Moreover, each node has a unique identity and a pair of public and private keys predistributed in the network.

3.2. Security Model

We define an attack as any action by an entity that results in disruption or degradation of the routing service. Attacks can divide into the following types.

Sybil Attack. In the Sybil attack [8], a malicious node can behave as if it were a larger number of nodes either by impersonating other nodes or simply by claiming false identities. In the geographic routing, a Sybil node could appear in more than one location at once. It can then tamper or forward the packets in a black hole or gray hole attack.

Rushing Attack. A malicious node in the rushing attack attempts to tamper packets and hurry them to the next hop node. In the traditional routing protocol, since only one packet is forwarded by the node, it would discard the legal one if it was forwarded by the adversary firstly.

Wormhole Attack. Two compromised nodes can communicate with each other by a private channel in the wormhole attack [11]. The adversary can tunnel the packet to another location and replay it there. A sensor node that hears a packet transmission directly from one wormhole node will consider itself to be a neighbor of that node.

Black Hole or Gray Hole Attack. In this type of attack, a malicious node drops all or part of the received traffic. The black hole attack is a type of attack in which a node supposed to relay packets discards all instead. The malicious node can also accomplish this attack selectively, which is rather called the gray hole attack.

Other Attacks. There are some other types of attacks, such as the blacklist attack, the replay attack, and the node selfish attack. However, since no information about adversaries is changed between nodes in ESGR, the blacklist attack can be avoided. The time stamp with the authentication mechanism can be used to prevent the replay attack. We treat the node selfish attack as the gray hole attack as the adversary also selectively drops packets for its own benefit.

We consider the denial-of-service attack, such as an attacker sending a high number of messages with meaningless packets, will be quickly identified by the authentication scheme. Moreover, attacks against lower layers such as the link or the physical layer are not addressed.

4. ESGR: Efficient and Secure Geographic Routing

ESGR is under the category of the general geographic routing, so it contains the following two parts.

4.1. Location Beacons

In this part, our scheme implements geographic leashes and provides an efficient broadcast authentication in the wireless sensor networks. We deploy efficient TESLA scheme [12] as it is based on the symmetric cryptographic primitives. TESLA requires loose time synchronization among all the communicating parties. In the network, we assume that all nodes share a synchronized clock with a maximum clock synchronization error of Δ. For simplicity, we assume the clock drift is negligible. ESGR location beaconing is composed of three phases: setup, sending location beacons, and verifying location beacons.

4.1.1. Setup

For the TESLA scheme, each node splits the time t into a series of intervals $I_{\mathrm{1}},\hspace{0.17em}{I}_{\mathrm{2}},\hspace{0.17em}\dots ,\hspace{0.17em}{I}_N$ , where t is the amount of time between rekeying. The duration of each time interval is $T_{\mathrm{int}}$ in common. We denote the starting time of the interval $I_i$ by $T_i$ , and $T_i=T_{\mathrm{0}}+i*T_{\mathrm{int}}$ , where $T_{\mathrm{0}}$ is the starting time of the entire hash chain. In each interval, the sensor node may send zero or multiple packets.

Consider the chain of length N with the values $K_{\mathrm{0}},\hspace{0.17em}{K}_{\mathrm{1}},\hspace{0.17em}\dots ,\hspace{0.17em}{K}_{N-\mathrm{1}}$ for time intervals $I_{\mathrm{0}},\hspace{0.17em}{I}_{\mathrm{1}},\hspace{0.17em}\dots ,\hspace{0.17em}{I}_{N-\mathrm{1}}$ . The sender picks the last key $K_{N-\mathrm{1}}$ of the key chain randomly and calculates the entire key chain using a pseudorandom function F to derive the previous keys: $K_i=F(K_{i+\mathrm{1}}{)}_{\forall i\in \{\mathrm{0},\dots ,N-\mathrm{2}\}}$ . The value $K_{\mathrm{0}}$ serves as a commitment to the entire chain, which allows anybody to authenticate the following values of the chain. Moreover, TESLA uses a second pseudorandom function $F^{\prime }$ to derive the key $K_i^{\prime }$ : $K_i^{\prime }=F^{\prime }(K_i)$ , which can be used to compute the Message Authentication Code (MAC) of the message for each time interval.

As TESLA requires an initially packet to authenticate the neighbor nodes, we achieve this authentication with a digital signature scheme, where the message is signed by the private key of the node. The initially authentication packet is transmitted by the sensor node with the identity $id$ as

$$\begin{array}{cc}& m=〈id,T_{\mathrm{int}},K_{\mathrm{0}},T_{\mathrm{0}},N,I_{\mathrm{0}},d〉,\text{Sign}\left(m\right),cert,\end{array}$$

(1)

where d is the key disclosure delay, $\text{Sign}(m)$ is the signature, and $cert$ is issued by the trusted Certificate Authority and prestored into the node. On receiving the initially authenticated packet, the neighboring nodes will verify the sender and record the associated parameters with the sensor's $id$ if valid.

4.1.2. Sending Location Beacons

The neighbors’ coordinates are updated periodically through one-hop beacons. Each node periodically transmits a beacon $B_j$ , containing its own identity $id$ and location $l_{id}=({id}_x,{id}_y)$ . Our mechanism extends the beacon to include the time stamp $I_i$ in the current time interval. Then the sender computes the MAC value over the beacon with the private key $K_i$ and broadcasts the packet to all the neighbors at the same time. For example, as shown in Figure 1, the construction of the packet in interval $I_i$ is

$$\begin{array}{cc}& B_j=\left\{id,{id}_x,{id}_y,I_i,e_j,P\left(B_{j+\mathrm{1}}\right)\right\},{\text{MAC}}_{K_i^{\prime }}\left(B_j\right),K_{i-d},\end{array}$$

(2)

where $P(B_{j+\mathrm{1}})$ is prediction outcome of the content of next beacon, $e_j$ is the sleep warning or work state with remaining energy, and the | stands for the message concatenation.

Figure 1

The TESLA scheme for location beacons when the key disclosure delay $d=2$ .

As the TESLA scheme inevitably introduces the additional delay by the key disclosure compared to other signature schemes, our beacon message appends the prediction outcome of next beacon $B_{j+\mathrm{1}}$ to overcome the drawback and provide faster authentication for the beacon packet. Then, we explain how to build the prediction outcome, as illustrated in Figure 1, $P(B_{j+\mathrm{1}})=H(id,{id}_x,{id}_y,I_{i+\mathrm{4}},e_{j+\mathrm{1}})$ , where H is a hash function. As the sensor node with the unique identity in our model is immobile, the identity and location information will be always the same. The changed information is the energy remainder of sensor node, which can be predicted by the sender in the current beacon according to the previous consumption model. Therefore, the location beacons are sent periodically and then predicted. However, how to build an accurate model to predict the energy consumption is orthogonal to our work.

The key remains secret for $d-\mathrm{1}$ time intervals. Packets sent at time interval $I_i$ can hence disclose the key $K_{i-d}$ if needed. Once the neighbors receive that key, they can verify the authenticity of the previous packets sent at interval $I_{i-d}$ . Note that if there is no beacon or packet sent in $I_{i+d}$ , the sender then transmits the secret key individually to the receivers for the purpose of verifying the beacon $B_j$ .

4.1.3. Verifying Location Beacons

When a neighbor node receives a beacon, it would verify each packet that the key used to compute the MAC of that packet is not yet disclosed by the sender. Considering the beacon $B_j$ arrives at the receiver at its local time $t_r$ , the security condition of TESLA [20] is that

$$\begin{array}{cc}& \lfloor \frac{t_r+\mathrm{\Delta }-T_{\mathrm{0}}}{T_{\mathrm{int}}}\rfloor <I_i+d.\end{array}$$

(3)

If this security condition is not satisfied, the receiver would drop the packet. Otherwise, it stores the packet and verifies the authenticity till it knows $K_i$ later. Then it recovers the commitment $K_{\mathrm{0}}$ by iteratively invoking the hash function and applies the valid key to check the stored MAC. Furthermore, when it has received an authenticated key $K_u$ in the reconstructed key chain, the receiver only needs to verify that $K_u=F^{i-u}(K_i)$ . If the authentication is valid, the receiver can update the key chain and store the latest authenticated key to improve the efficiency of verification. Furthermore, to achieve instant authentication and verify the following $B_{j+\mathrm{1}}$ after receiving $B_j$ in our example, the receiver first verifies $B_j$ , gets the prediction outcome $P(B_{j+\mathrm{1}})$ from the beacon $B_j$ , and then checks whether the recomputed value matches $P(B_{j+\mathrm{1}})$ given relevant values in the $B_{j+\mathrm{1}}$ .

After verifying the packet, the node could obtain the coordinates of the sender's location $l_S=(S_x,S_y)$ in the beacon and cache it with the identity in the neighbor list. Then the receiver measures the correctness of the location information based on the geographic leashes, which is based on the radio propagation model. Assuming that the transceiver gain is set to be one and the channel bandwidth exactly matches, we define α as the path loss factor, which depends on the environment. The relationship between the received signal strength $P^d$ and the distance $d_{SQ}$ from the sender S to the receiver Q can be expressed as (4), where C is the speed of the radio and f is the frequency of the radio [9, 29]:

$$\begin{array}{cc}& P^d=\frac{P_t{C}^{\mathrm{2}}}{{\left(\mathrm{4}\pi \right)}^{\mathrm{2}}{d}_{SQ}^{\alpha }{f}^{\mathrm{2}}}+\epsilon .\end{array}$$

(4)

Here, $P_t$ means the setting transmission power and ε is represented as a zero-mean Gaussian random variable. The maximum relative error of the distance is considered to be δ. We denote the coordinates of the receiver's location by $l_Q$ . The value of $d_{SQ}$ is constrained by the following inequality: $d_{SQ}\le \hspace{0.17em}\parallel l_S-l_Q\parallel +\hspace{0.17em}\delta$ . Due to the inequality, the receiver weights the location trusted information ${\text{LT}}_S$ of the sender to be zero or one, which is used to construct the trust model in the next part.

4.2. Data Packets

4.2.1. Distributed Trust Model

For detecting routing attacks in a WSN, we design a distributed trust model which enables each node to define the trustworthiness of its neighbors combining the location trusted information and direct trusted information.

We now explain the direct trusted information. To further detect neighbor nodes dropping or selectively forwarding packets, the sender overhears the wireless channel to check whether the packet is actually forwarded by its selected next hop node. Meanwhile, it enforces efficient authentication according to the TESLA scheme. We assume that the average number of packets sent to node F for forwarding is marked as $Q_F$ and the average number of valid data transmissions of node F is marked as $V_F$ . The metric of direct trust can be given by ${\text{DT}}_F=V_F/Q_F$ . Initially, $Q_F=\mathrm{1}$ , $V_F=\mathrm{0}$ . Finally, the total trust value for node F is produced by combining the location trusted information and direct trusted information:

$$\begin{array}{cc}& T_F=\eta ·{\text{DT}}_F+\left(\mathrm{1}-\eta \right)·{\text{LT}}_F,\end{array}$$

(5)

where η is the factor with $\mathrm{0}<\eta <\mathrm{1}$ . As the number of interactions increases, the direct trusted information becomes more significant than the location trusted information; thus η can be modified to a larger value.

4.2.2. Opportunistic Forwarding

When the source prepares to send a message M, it will first encrypt the message M with a symmetric key K sharing with one of the sinks. As the intermediate node in the routing path needs some information such as the unique identifier of the packet, the source node will then put the necessary and constant information in the header field marked as $HI$ , which is also contained in the message M. Then, the source (or intermediate) node R begins to calculate the metrics of all the neighbors and establish its own forwarder list. Supposing that the distance from the sender to the sink is $D_R$ and the distance from its neighbor F to the sink is $d_F$ , the routing metric can be given by

$$\begin{array}{cc}& {\text{metric}}_F={\beta }_{\mathrm{1}}·\left(\mathrm{1}-\frac{d_F}{D_R}\right)+{\beta }_{\mathrm{2}}·T_F+{\beta }_{\mathrm{3}}·e_F,\end{array}$$

(6)

where $e_F$ is the remaining energy of node F which is perceived by node R through frequent location beacons and ${\beta }_i$ is the coefficient factor ( $\mathrm{0}<{\beta }_i<\mathrm{1}$ and ${\beta }_{\mathrm{1}}+{\beta }_{\mathrm{2}}+{\beta }_{\mathrm{3}}=\mathrm{1}$ ). The routing metric is an integrated set of trust, energy, and progress to the sink. Based on (6), each valid neighbor is assigned a metric value, and the one with the largest metric will have the highest priority.

The forwarder list is established according to the routing metric, and we set the number of candidates for the next hop to be N: $C_{\mathrm{1}},C_{\mathrm{2}},\dots ,C_N$ . For example, as shown in Figure 2, node R's candidate nodes for the next hop are nodes A, B, and C with $N=\mathrm{3}$ . If $Num$ is less than N, it will be filled with $\text{pad}$ to ensure the packet length unchanged. The payload of the forwarding data packet can be expressed as

$$\begin{array}{cc}& HI,E_K\left(M\right),H\left(E_K\left(M\right)\right),Num,C_{\mathrm{1}},C_{\mathrm{2}},\dots ,C_N,I_d,\end{array}$$

(7)

where H is the hash function, $E_K(·)$ is one of symmetric encryption algorithms with the secret key K, and $I_d$ is the current time interval. The format of $HI$ is given by:

$$\begin{array}{cc}& {id}_{\text{source}}\parallel sequence\parallel {id}_{\text{sink}}.\end{array}$$

(8)

Figure 2

An illustration of the opportunistic forwarding scheme. For node R, the forwarder list includes nodes A, B, and C. The packet is then transmitted to node A, and node A establishes its forwarder list including nodes E, F, and G.

The identity of the source ${id}_{\text{source}}$ plus the sequence number $sequence$ marks a unique data packet in the network. Therefore, $HI$ is unique, so is $H(E_K(M))$ . The source (or intermediate) node will store the values of $HI$ and $H(E_K(M))$ for each new incoming packet in its ID list. The data packet with MAC attached is then broadcast to the neighbors. After the transmission, the sender would also monitor the next hop's transmission and adjust the direct trusted value by collecting the next hop's feedback information.

The receiver within the source (or intermediate) node's transmission range could receive and verify the packet. The validation process can be divided into two steps and operate as follows. First, the neighbor node will authenticate the sender of the incoming packet with the TESLA scheme. Then, it will look for its ID list and compare the values of $HI$ plus $H(E_K(M))$ of the packet with the cached ones. If the packet has been received, these values are exactly equal and the receiver would drop the packet.

After successful validation, if a node finds itself to be the first candidate in the forwarder list (in our example, node A or node E), it would establish its own forwarder list by calculating each neighbor's metrics and immediately send the data packet. However, if it finds itself not the first candidate in the forwarder list (e.g., node B, node C, node F, or node G), the packet will be cached for a while according to the priority determined by the forwarder list. For example, if there are k nodes ahead, it will wait for k time slots before forwarding that packet. The cached packet is attached a counter which will minus one every time. During the waiting, if it receives an incoming packet that has the same $HI$ plus $H(E_K(M))$ recorded in the ID list, the corresponding cached packet will be discarded as it must be relayed by another candidate with higher forwarding priority (e.g., node A or node E). When the counter returns to zero, the cached packet will be forwarded. Subsequent nodes follow the same process until the packet reaches the destination.

5. Security and Efficiency Analysis

5.1. Security Analysis

In this section, we specify how ESGR addresses the major attacks described in Section 3.

5.1.1. Sybil Attack

In the Sybil attack, the authentication and geographic leashes mechanism in ESGR can be used to detect it. Each node in the network corresponds to a location point and a unique pair of public and private keys. For efficiency, when a beacon or a data packet is sent by a node, it requires to be signed with a key of TESLA scheme. Moreover, as the key can be authenticated by a commitment and the commitment is signed by the node's private key, the adversary cannot easily impersonate other node and appear in more than one location at the same time. If the adversary claims false location in the beacon, the neighbor nodes can use the geographic leashes for verification to defend against the attack. Even if the adversary is lucky to avoid the detection, our ESGR can deal with the misbehavior like black hole or gray hole attack as soon as these Sybil nodes become packet droppers.

5.1.2. Rushing Attack

In the rushing attack, the adversary tries to block the communication by hurrying its modified packets to the next hop node of routing path. As one of the opportunistic routings, ESGR has more candidates to relay the data packets. For each valid packet determined by both the fields of $HI$ and $H(E_K(M))$ , it can avoid the tempering attack incurred by rushing attack. The nodes in ESGR forward every copy of the packets even if only one of the fields is identical. As a result, the correct packet will reach the destination though it also receives some redundant packets.

5.1.3. Wormhole Attack

ESGR verifies the locations of the neighbors by the geographic leashes and then obtains the results of validations. Followed by a low location trusted value, ESGR can alleviate the consequences of the wormhole attack. Furthermore, after the adversaries have taken control of a fraction of the traffic through creating the wormholes, they would maliciously drop or corrupt packets, which would be alleviated by the distributed routing metric in our scheme.

5.1.4. Black Hole or Gray Hole Attack

Under the black hole or gray hole attack, the number of the packets received by sink nodes in the network will decrease largely. ESGR can ensure the throughput when the malicious nodes drop or selectively drop data packets, as potential multiple paths are available in the opportunistic forwarding scheme. Even when there are many black hole attackers, our path can avoid selecting them for the next hop with their low trust values.

As illustrated in Figure 3, consider that node A is a new black hole and node F is an existing gray hole node. A packet is forwarded by node R to the sink, and the forwarder list is node A, node B, and node C. In case node A is selected as the first candidate, the packet would be dropped. Then, node B as the second candidate will relay the packet to node F, G, or H for the next hop instead of node A and suppress the lower priority candidate's forwarding (node C). We assume that node B suspects that node F is an adversary due to its low trust value. With the largest routing metric, node G would be selected as the first candidate with the highest priority by node B. The packet would be transmitted to node G and then forwarded to the sink. Moreover, as node R does not receive the packet sent by node A, our routing mechanism decreases the direct trusted value ${\text{DT}}_A$ thus lowering the routing metric ${\text{metric}}_A$ for node A. When node B succeeds in delivering the packet, node R increases and updates its routing metric ${\text{metric}}_B$ . Therefore, after a period of time, node R may select node B as the first candidate with the highest priority for the following packets.

Figure 3

An illustration of black hole attack and gray hole attack. Node A is a black hole node. Node F is a gray hole node.

5.2. Efficiency Analysis

We conduct the theoretical analysis of PDR and end-to-end delay performance.

5.2.1. Packet Delivery Rate

Assume there are maximum N forwarding candidates. Suppose $p_x$ is the probability that the data packets are dropped by the candidate node. The analytical packet delivery ratio is the end-to-end probability that a packet is successfully delivered from a source to the sink:

$$\begin{array}{cc}& P_{\text{ESGR}}={(\mathrm{1}-p_x^N)}^{L-\mathrm{1}},\end{array}$$

(9)

where L is the average hop for the packet. For simplicity, we assume the per-hop packet delivery is independent of each other.

For GPSR like unicast routing protocol, the packet delivery ratio is denoted as follows:

$$\begin{array}{cc}& P_{\text{unicast}}={(\mathrm{1}-p_x)}^{L-\mathrm{1}}.\end{array}$$

(10)

We can see that the opportunistic routing significantly improves the packet delivery rate compared with the ordinary unicast routing.

5.2.2. End-to-End Delay

In order to measure the end-to-end delay in theory, we study the per-hop packet forwarding delay of the Qth candidate. It is divided into two parts: one part is introduced by the sender and the other comes from the candidate coordination:

$$\begin{array}{cc}& \mathrm{\Delta }{T}_{\text{ESGR}}=t_s+\left(Q-\mathrm{1}\right)·\mathrm{\Delta }T,\end{array}$$

(11)

where $\mathrm{\Delta }T$ represents the given time slot and $t_s$ denotes the packet transmission delay in the corresponding normal situations. Assume the Qth forwarder relays the packet for one transmission on average; then

$$\begin{array}{cc}& Q={\displaystyle \sum }_{i=\mathrm{1}}^N‍i\left(\mathrm{1}-p_x\right)·p_x^{i-\mathrm{1}}+N·p_x^N.\end{array}$$

(12)

Since ESGR is one of the opportunistic routings, we make use of the broadcast nature that all nodes within the coverage of the sender would receive the signal. To decrease the packet loss, some alterations are encouraged on the RTS/CTS/ACK mechanism in 802.11b like [15]. The packet is sent in unicast form and takes the first candidate as the next hop. On the receiver side, if the message's next hop is not the receiver, it is also delivered to the upper layer and then processed by ESGR. The sender delay includes four parts: channel contention time for 802.11b ( $T_c$ ), data transmission time ( $T_{\text{data}}$ ), propagation delay ( $T_p$ ), and the key disclosure delay for authentication ( $T_{\text{key}}$ ). Then, $t_s=T_c+T_{\text{data}}+T_p+T_{\text{key}}$ .

Therefore, the end-to-end packet transmission delay of ESGR can be expressed as follows:

$$\begin{array}{l}{T}_{\text{ESGR}}=\mathrm{\Delta }{T}_{\text{ESGR}}·L\\ =(\phantom{{\displaystyle \sum }_{i=\mathrm{1}}^N‍}{T}_c+T_{\text{data}}+T_p+T_{\text{key}}\\ \phantom{\mathrm{11}}\phantom{1}+\left({\displaystyle \sum }_{i=\mathrm{1}}^N‍i\left(\mathrm{1}-p_x\right)·p_x^{i-\mathrm{1}}+N·p_x^N-\mathrm{1}\right)·\mathrm{\Delta }T)·L\end{array}$$

(13)

while the end-to-end delay of unicast routing with $N=\mathrm{1}$ is given by $T_{\text{unicast}}=(T_c+T_{\text{data}}+T_p+T_{\text{key}})·L$ .

We can find that with a larger value of N, the packet delivery rate is higher but the end-to-end delay is also larger. In our simulation, we will show how the candidate number affects both the performances of PDR and delay.

6. Simulation

The performance of ESGR is evaluated by the OPNET network simulator, together with the geographic routing protocol GR (the version with perimeter forwarding switched off GPSR) and the zone routing protocol ZRP. We employ the propagation model of two-ray ground. Moreover, we use the AES algorithm for encryption with secret key of 128 bits. The length of MAC or the hash key is 80 bits. The time slot of opportunistic routing is set to be 10 ms. Some other important parameters are set in Table 1. The performance metrics consist of the packet delivery rate, the end-to-end delay, and the bandwidth of overhead.

Table 1

Experimental setup.

Parameter	Value
Plane size	1 km by 1 km
Number of nodes	50~300
Medium access control	802.11 b at 1 Mbps
Transmission range	250 m
Traffic size	512 Bytes
Number of candidates	$N=\mathit{3}$
Number of flows	10 CBR, 2 packets/s
Parameter	$\eta =\mathrm{0.7}$ , ${\beta }_{\mathrm{1}}=\mathrm{0.4}$ , ${\beta }_{\mathrm{2}}=\mathrm{0.4}$ , ${\beta }_{\mathrm{3}}=\mathrm{0.2}$

6.1. Node Density

A number of nodes are placed randomly in a square area of 1000 m. We assume that one fifth of the nodes in the network are the black hole nodes. We measure the performance of all the protocols in different sized networks, with the increasing node density.

Figure 4 shows the performance of packet delivery rate. Due to one of the opportunistic routings, the PDR of ESGR is the highest in all the scenarios with different network size. In the network of 300 nodes, ESGR outperforms the GR and ZRP protocols and enables more than 95% packet delivery rate on a $\mathrm{1000}\hspace{0.17em}\text{m}*\mathrm{1000}\hspace{0.17em}\text{m}$ place with 60 black hole nodes. The differences of PDRs are not distinct for geographic routings under various node densities.

Figure 4

Packet delivery rate for different node densities.

The overhead is measured by the extra bits per second for data transmissions. When the number of sensor nodes increases, the overheads of three protocols also increase as the density of neighbor nodes becomes larger. As shown in Figure 5, the node density impacts the effectiveness of ZRP by the decrease of the throughput. Although ESGR has a larger overhead than GR, it is still accessible for the network's load.

Figure 5

Overhead for different node densities.

From the simulation results, ESGR has 1.5 times higher PDR than the other two protocols and keeps stable with an acceptable growing overhead when the network size grows large.

6.2. Proportion of Malicious Nodes

We assume that the network size is 100 nodes. The proportion of malicious nodes in the network varies from 0.1 to 0.7. The malicious nodes would drop or tamper the data packets that introduces packet loss. We consider these attacks leading to packet dropping to be black hole and gray hole attacks as they have the same consequences. Then, black hole nodes would drop all the packets that they have received. For gray hole nodes, the probability of packet loss is set to 0.5.

As shown in Figures 6 and 7, the insecure routings GR and ZRP are very sensitive to malicious nodes. The delivery rate falls rapidly even with a small percentage of gray hole nodes. The simulation results also indicate that malicious nodes do not deeply affect the delivery rate of our ESGR. The packet delivery rate falls from close to 100% to more than 85% when half of the sensor nodes are black hole nodes. They can be detected by our distributed trust model, and more candidates in the opportunistic routing are used for transmissions to improve the PDR. We can also find that the performances across all protocols against the gray hole attack are similar to those against the black hole attack. When half of sensor nodes become gray hole nodes and lose packets with a probability of 50%, ESGR can achieve the delivery rate of more than 95% while GR and ZRP only obtain the PDR of approximately 60% in the hostile sensor networks.

Figure 6

Packet delivery rate and end-to-end delay for different proportions of black hole nodes.

Figure 7

Packet delivery rate and end-to-end delay for different proportions of gray hole nodes.

As the proportion of malicious nodes is increasing, the average end-to-end delays of GR and ZRP decrease. However, the delay in ESGR grows in the hostile network, as it adopts more candidate nodes to ensure the throughput at the expense of some delay. The link breaks because the black hole or gray hole nodes would introduce suboptimal candidate to relay the data packets. The delay of such packets would raise the average delay. Moreover, the TESLA scheme also introduces the authentication delay, which is one part of the end-to-end delay performance.

Therefore, ESGR can maintain an uninterrupted and secure communication while the delay is growing within the scope of permission.

6.3. Candidate Number

The number of candidates could affect the performance of ESGR, as simulated in a network with 200 nodes. The more forwarding candidates are in the network, the higher delivery rate could be achieved to improve the robustness, as shown in Figure 8. Nevertheless, the improved gain becomes slower when N continues increasing. The measured results are almost consistent with our theoretical analysis in Section 5.

Figure 8

Packet delivery rate for different candidate numbers.

The simulation result of the end-to-end delay performance is shown in Figure 9. When many normal nodes become black holes, they would often block the communication leading to a high probability of packet dropping. As a result, the increasing value of Q aggravates the average delay. While many forwarding candidates have joined to relay packets, the step of the PDR improvement becomes narrow and the end-to-end delay would increase due to the long one-hop delay during a successful delivery. In our comparisons, we ignore the correlation of per-hop in the theoretical analysis, which contributes to the difference between the simulated and the theoretical results.

Figure 9

End-to-end delay for different candidate numbers.

7. Conclusion

In this paper, we design and present an efficient and secure geographical routing against a series of attacks. ESGR requires associative one-way hash function and TESLA mechanism for security. It also makes use of the broadcast nature of wireless channel and forwards packets based on the opportunistic approach. Furthermore, our routing metric is combined with a novel distributed trust model to defend against packet tempering and dropping incurred by the Sybil attack, wormhole attack, black hole attack, and so forth.

ESGR is evaluated under various network configurations such as node density, proportion of malicious nodes, and candidate number. We show that the protocol can tolerate the existence of the malicious nodes and still maintain a high throughput at the expense of some acceptable delay in hostile sensor networks. In the future work, the mobility of sensor nodes will be introduced in the network scenarios, and extended analysis against collusion attacks will be conducted.