ESecRout: An Energy Efficient Secure Routing for Sensor Networks *

Abstract

In this paper, we present an Energy Efficient Secure Routing Protocol for Sensor Networks (ESecRout). The protocol uses the symmetric cryptography to secure messages, and uses a small cache in sensor nodes to record the partial routing path (previous and next nodes) to the destination. It guarantees that the destination will be able to identify and discard the tampered messages and ensure that the messages received are not tampered with. Simulation shows ESecRout's performance comparison with the non-secure routing protocol AODV [1] and the secure routing protocol SAODV [2]. Our protocol needs a little more route discovery overhead (about 8%) and costs a little more energy (about 8%) than AODV, but it performs much better than SAODV which needs much more route discovery overhead (about 33%) and costs much more energy (35%) than AODV. Simulation results also show that the packet delivery ratio and packet latency of AODV, SAODV, and ESecRout are almost the same. Thus, we show that our protocol ESecRout provides energy efficient secure routing.

Keywords

Routing Security Sensor Networks

1. Introduction

For many sensor network applications, security is one of the most important aspects [3, 4]. Secure routing protocols in sensor networks present challenges due to resource limitations [3], the ad hoc nature, and no centrally administered secure routers. An existing route could be broken down or a new route could be prevented from being established because of the attacks [5 –7]. There are several examples of such attacks against routing in sensor networks. For instance, the routing packet is dropped or tampered with; the attacker inserts spurious messages in the sensor network.

To preserve the power of sensors, we propose an Energy Efficient Secure Routing for Sensor Networks called ESecRout. Since the communication over radio is an energy-consuming function performed by the sensor devices, we need to minimize communications overhead [3]. In the ESecRout protocol, the two-level architecture is used to safeguard the sensor network and to minimize the communication overhead. In this architecture, the sensor network is divided into clusters with one cluster head for each cluster. The nodes in the cluster send the data to the cluster head instead of sending data directly to the sink node (the destination node). Then, the cluster head aggregates the data from the sensor nodes in the cluster and sends it to the sink node. The two-level architecture lowers the message overhead. It can greatly save the energy consumption, and decreases the usage of memory and bandwidth.

The ESecRout protocol guarantees that the sink node will be able to identify and discard the tampered messages and ensure that the accepted messages are not tampered with. The asymmetric cryptography algorithms [8 –10] for cryptography and authentication are not suitable for sensor networks due to the large computation and communication overhead. The ESecRout protocol uses only symmetric cryptography to secure the messages, and uses a small cache in sensor nodes to record the partial routing path (previous and next nodes) to the sink node. Due to the frequent communications in the cluster, we use a cluster key in the cluster to secure messages. The cluster head uses the preloaded key to secure aggregated messages before sending them to the sink node.

On comparing the performance with the non-secure routing protocol AODV [1] and the secure routing protocol SAODV [2], the ESecRout protocol needs a little more route discovery overhead (about 8%) and costs a little more energy (about 8%) than AODV, but it performs much better than SAODV since it needs much more route discovery overhead (about 33%) and costs much more energy (35%) than AODV. In addition, we show that ESecRout has the same packet delivery ratio and latency as in AODV and SAODV.

This paper is the extended version of the paper [11]. In this extended version, in the performance evaluation part, we have added the comparison between ESecRout and SAODV protocol. We have also added two more experiments such as the route discovery byte overhead and the route discovery energy consumption overhead. In the analysis part, we have added the cost analysis which includes the complexity analysis, storage analysis, and energy consumption analysis of all three protocols.

In the remainder of the paper, the detailed protocol description is given in Section 2. Section 3 describes security analysis. Section 4 provides performance evaluation of the ESecRout protocol. Section 5 addresses the related works. We conclude in Section 6.

2. Secure Routing Protocol

In the proposed ESecRout protocol, we assume that every node has a unique identity (ID) and a preloaded key [5]. The network is divided into clusters after self-organization [12] and each cluster has a cluster head, which knows the ID of the sensor node in its cluster. The sensor node knows the ID of its cluster head. The sink node knows the topology of the sensor network after self-organization. We assume that the sink node is a super node, with more power and memory. It stores a table containing (ID, Key) pairs of all the sensor nodes. In the proposed ESecRout protocol, we have one secured and trusted sink node but all other sensor nodes can be compromised.

We build the secure route from the source node to the sink node using the ESecRout protocol. We guarantee that a packet reaches the sink node even if malicious nodes exist on the route. It guarantees that the message is originated from the authenticated source node and is not tampered with on the route. In the secure route discovery, the malicious node on the route can be detected. Therefore, the route created using our route discovery protocol is secure. The ESecRout protocol has the following four features:

1)
The routing packet and data packet are very small because they only include the partial path information. We do not use the source routing because in the source routing the identities of the traversed intermediate nodes are accumulated in the route request [13], which increases the message overhead.
2)
We build the route before continuously sending the data to the sink node along the route. We do not flood the data packet to the sink node because it costs more communication overhead when continuously sending the data packets, and moreover the data packet has a much bigger size than the routing packet.
3)
It uses the two-level architecture; the cluster head aggregates the data, and then sends it to the sink node along the route which lowers the communication overhead.
4)
It only uses high efficient symmetric cryptographic operations to secure messages, which lowers the communication overhead and saves the energy of the sensor nodes. The asymmetric cryptography is unsuitable to be used in the sensor network due to the large computation and communication overhead. Table 1 provides the notation description which will be used in this paper.

Table 1
Notation Description

Notation Description

A, B Principles, such as sensor nodes

M₁|M₂ The concatenation of messages M₁ and M₂

K _A The secret key held by A

MAC(K,M) The message authentication code of message M using a symmetric key K [14]

E_K(M) Encryption of message M with key K [15]

N _A A nonce generated by node A, which is a random number

ID _A The identity of node A

2.1. Secure Route Discovery

Notation	Description
A, B	Principles, such as sensor nodes
M₁\|M₂	The concatenation of messages M₁ and M₂
K _A	The secret key held by A
MAC(K,M)	The message authentication code of message M using a symmetric key K [14]
E_K(M)	Encryption of message M with key K [15]
N _A	A nonce generated by node A, which is a random number
ID _A	The identity of node A

The source node initiates the route discovery process through sending the route request (RREQ) to the sink node. When the sink node receives the RREQ, it creates the route reply (RREP) to the source node. After the route discovery, every node along the route will have the appropriate routing table.

2.1.1 Secure Route Request

The Source node initiates the route discovery by broadcasting the RREQ to its neighbors, which is constructed as follows:

{I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e} | M A C (K_{s o u r c e}, I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e})}

where ID_RREQ is a random number.

The intermediate node only accepts the first RREQ according to ID_RREQ. The routing table is updated through adding the ID of the previous two hops, ID_source, and ID_RREQ. Then, it updates the RREQ. It adds its ID to the RREQ which is directly from the source node. It replaces ID_this, ID_pre embedded in the RREQ with its previous and current ID if the RREQ is from other nodes. Finally, it broadcasts the updated RREQ, which is constructed as follows:

{I D_{t h i s} | I D_{p r e} | I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e} | M A C (K_{s o u r c e}, I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e})}

where ID_pre and ID_this are the IDs of the previous and the current node.

When the sink node receives the RREQ, it gets the key of the source node from the (ID, Key) pair table, which is used to verify the MAC. It only accepts the first RREQ with the valid MAC according to the source node and ID_RREQ. Then it stores ID_source, ID_RREQ and previous two hops in the routing table.

2.1.2 Secure Route Reply

When the sink node accepts the RREQ, it constructs the RREP as follows:

{I D_{p r e} | I D_{t h i s} | I D_{n e x t} | I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{sin k} | M A C (K_{s o u r c e}, I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{sin k})}

where ID_next is the ID of the next node. Then it broadcasts it.

The intermediate node with the same ID as the ID_pre embedded in the RREP updates the ID_pre, ID_this and ID_next in the RREP with the IDs of its previous, current, and next nodes. Then it broadcasts the updated RREP packet. Simultaneously it updates its routing table to add IDs of the next two hops. If it cannot get acknowledgement from its next hop within the specified time, the previous node may be a malicious node. It drops any other RREQs during the next route discovery. If it detects the RREP broadcasted by its previous hop with the wrong ID_pre since it stores two previous hops in its routing table, it blocks its previous hop which may be a malicious node.

The source node verifies the MAC after it receives the RREP. If the verification succeeds, it inserts the IDs of the next two hops on the route to its routing table. After the route discovery, the intermediate node has the routing table as shown in Table 2. If the node reaches the maximum number of routes in the routing table and if the new routes come, it deletes the oldest route in its routing table.

Table 2
Routing Table

Source Node Previous Two Hops Next Two Hops

ID _source1 ID_pre2, ID_pre1 ID_next1, ID_next2

ID _source2 ID_pre2, ID_pre1 ID_next1, ID_next2

ID _sourceN ID_pre2, ID_pre1 ID_next1, ID_next2

Source Node	Previous Two Hops	Next Two Hops
ID _source1	ID_pre2, ID_pre1	ID_next1, ID_next2
ID _source2	ID_pre2, ID_pre1	ID_next1, ID_next2
ID _sourceN	ID_pre2, ID_pre1	ID_next1, ID_next2

2.1.3 Secure Route Maintenance

If a sensor node has no route in its routing table at the time it starts sending the data, it initiates the route discovery. If the source node gets the error message after it sends data or the routing packet, it triggers a new route discovery.

2.2. Secure Data Forwarding

Recall that the ESecRout protocol is based on the two-level architecture. The cluster heads are at the higher level, and the other nodes are at the lower level. The cluster head aggregates the data from the nodes in its cluster. Then it sends it to the sink node. We use the cluster key to provide the secure communication in the cluster. The cluster key can be established during the self-organization [5]. We use the preloaded key to secure the message which is sent to the sink node.

2.2.1 Secure Data Forwarding in the Cluster

A sensor node sends the data packet to its cluster head using the cluster key, which is constructed as follows:

{I D | E_{C K} (d a t a) | M A K [C K, I D | E_{C K} (d a t a)]}

where ID is the ID of the cluster head, and CK is the cluster key shared by the nodes within the cluster. The node with the same ID as the ID embedded in the data packet such as the cluster head verifies the MAC. If the verification succeeds, it decrypts the data using the cluster key. Then it aggregates the data from the sensor nodes in the cluster, and constructs the data packet which will be sent to the sink node.

2.2.2 Secure Data Forwarding among the Clusters

The cluster head becomes the source node after it aggregates the data. If there is a route in the routing table, it constructs the following data packet:

\begin{aligned} {I D_{t h i s} | I D_{n e x t} | I D_{s o u r c e} | I D_{sin k} | Q_{I D} | E_{K_{s o u r c e}} (d a t a) | M A C [K_{s o u r c e}, I D_{s o u r c e} \\ | I D_{sin k} | Q_{I D} | E_{K_{s o u r c e}} (d a t a)]} \end{aligned}

where Q_ID is the Query ID from the sink node, which is a random number. Then it broadcasts it.

The intermediate node with the same ID as the ID_next embedded in the packet will rebroadcast the updated packet, where the ID_this and ID_next are replaced by its ID and the ID of the next hop in the routing table. Other intermediate nodes drop the packet.

If the source node can not receive the packet again that the next hop rebroadcasts, it triggers a new route discovery. If the intermediate node cannot get the packet broadcasted by the next hop within a certain time, it reports the error message to the source node. Simultaneously it also adds the next hop in its blacklist. It will not accept the RREP from the node in its blacklist. After the sink node receives the packet, it verifies the MAC using the key of the source node from the (ID, Key) pair table. If the verification succeeds, it gets the result by decrypting the encrypted data.

2.2.3 Further Data Verification

After the sink node gets the data packet, two operations need to be executed:

1)
the sink node compares the replies from other cluster heads which are residing the neighboring clusters of the source node;
2)
the sink node will compare the replies with the history record.

If the data packet is abnormal, the sink node must verify it by sending the further request query to the nodes in the cluster as shown in Fig. 1. They broadcast the result of the request query to the sink node, which is constructed as follows:
${I D_{s o u r c e} | I D_{sin k} | Q_{I D} | E_{K_{s o u r c e}} (d a t a) | M A C [K_{s o u r c e}, I D_{s o u r c e} | I D_{sin k} | Q_{I D} | E_{K_{s o u r c e}} (d a t a)]}$

Figure 1.
Reply verification.

The sink node continues the further analysis after it receives the further result from these nodes.
2.3. Secure Query Dissemination

There are two cases, the sink node wants to get the information from a particular area or from the whole sensor network. According to these two scenarios, the request query (reqQ) is respectively sent to a particular area or the whole sensor network.

2.3.1 Query a Particular Area

The sink node checks its routing table whether the route to the cluster head of that area exists. If yes, it sends the reqQ packet to the cluster head of that area, which is constructed as follows:

\begin{aligned} {I D_{t h i s} | I D_{p r e} | I D_{sin k} | I D_{s o u r c e} | Q_{I D} | E_{K_{s o u r c e}} (r e q Q) | M A C [K_{s o u r c e}, I D_{sin k} \\ | I D_{s o u r c e} | Q_{I D} | E_{K_{s o u r c e}} (r e q Q)]} \end{aligned}

Otherwise, it broadcasts the reqQ packet to the cluster head, which is constructed as follows:

{I D_{sin k} | I D_{s o u r c e} | Q_{I D} | E_{K_{s o u r c e}} (r e q Q) | M A C [K_{s o u r c e}, I D_{sin k} | I D_{s o u r c e} | Q_{I D} | E_{K_{s o u r c e}} (r e q Q)]}

When the cluster head receives the query request packet, it verifies the MAC. If the verification succeeds, it decrypts the reqQ using its secret key. Then it sends the reqQ to the nodes in that cluster using its cluster key, which is constructed as follows:

{I D | E_{C K} (r e q Q) | M A C [C K, I D | E_{G K} (r e q Q)]}

where ID is the ID of the cluster head, and CK is the cluster key. The nodes in the cluster receive reqQ after they decrypt the packet using the cluster key.

2.3.2 Query the Whole Sensor Network

The sink node broadcasts the plaintext reqQ, which can be eavesdropped, modified, or dropped by the malicious node. However, the reqQ can reach any sensor node even if a malicious node drops it because of broadcast. The sensor nodes get the query result according to the reqQ. The query result is the most important. In our approach, either the sink node gets the correct information or it detects that the tampered query reply. The query reply ReplyQ is constructed as follows:

\begin{aligned} {I D_{t h i s} | I D_{n e x t} | I D_{s o u r c e} | I D_{sin k} | Q_{I D} | (r e q Q) | E_{k_{s o u r c e}} (d a t a) | M A C [K_{s o u r c e}, I D_{s o u r c e} \\ | I D_{sin k} | Q_{I D} | r e q Q | E_{K_{s o u r c e}} (d a t a)]} \end{aligned}

Then the sensor node applies the same technique as data forwarding process. But unlike data forwarding, the query reply includes the reqQ, which is also authenticated using MAC. If a malicious node modifies the reqQ, the sink node can verify it using MAC.

3. Theoretical Analysis

This section gives security analysis and cost analysis of the ESecRour protocol described in earlier sections. We also these two costs compare ESecRout with SAODV and AODV protocols.

3.1. Security Analysis

In this section, we analyze the security threats and show how the ESecRout protocol mitigates these threats. Several attacks [4, 16] can be launched against the routing in the sensor network such as:

Message tempering attack: An attacker can alter the content of routing and data messages and forward them with the falsified information.

Message dropping attack: An attacker can intentionally drop the routing and data messages.

These attacks may endanger the routing establishment and data forwarding in the sensor network. In the ESecRout protocol, we consider a single node as the malicious node which makes the message tampering attack, or message dropping attack. The attack such as the wormhole attack [4, 16] is not considered, where several nodes collude to make the attack against the route establishment.

To help the security analysis for the SecRout protocol, two scenarios are considered according to the location of the malicious nodes. First, the source node is a normal node, but the intermediate node is a malicious node to make attacks; the second, the source node is a malicious node to make attacks.

If the intermediate node is a malicious node, it can perform the following three actions:

1)
Broadcast;
2)
Drop;
3)
Modify. (See Fig. 2)

Figure 2.
Sensor networks embedded malicious nodes.
3.1.1 Intermediate Node Broadcasts Messages

In the RREQ process, the intermediate node broadcasts the updated RREQ and creates the routing table. The malicious node (Node M) may have three choices to attack this process:

Case 1: The next hop (Node N) records the wrong ID of the previous node in its routing table. When the RREP reaches Node N, it is updated using the tampered ID of the previous node. Other nodes drop this RREP since their ID does not match the tampered ID. The node N detects that its previous hop is a malicious node since it cannot hear its rebroadcast. Then it refuses to broadcast other RREQs and the sink node selects other routes during next route discovery.

Case 2: When the RREP packet reaches Node M, it broadcasts it with a wrong ID of the previous node since it has incorrect information in its routing table. Node N can detect the tampered RREP broadcasted by Node M since its routing table stores two previous hops. Therefore, it blacklists Node M.

Case 3: If Node M broadcasts the RREQ with the wrong ID of its previous node, the previous node can detect it through comparing its ID with the ID of the previous node embedded in the RREQ. It blacklists the malicious node M and informs the source node. The source node blocks the malicious node M. It triggers another route discovery with the RREQ as follows:

{I D_{M} | I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e} | M A C (K_{s o u r c e}, I D_{M} | I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e})}

If the malicious node M receives the RREQ, it broadcasts the updated RREQ as follows:

\begin{aligned} {I D_{t h i s} | I D_{p r e} | I D_{M} | I D_{s o u r c e} | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e} | M A C [K_{s o u r c e}, I D_{M} | I D_{s o u r c e} \\ | I D_{sin k} | I D_{R R E Q} | N_{s o u r c e})} \end{aligned}

Its neighbors ignore it since the ID_M is the same as the ID_this embedded in the RREQ. If Node M tampers ID_this and rebroadcasts it, it is similar to Case 1 of the RREQ process. If Node M tampers ID_M, the sink node can detect it when it verifies the MAC.

In the RREP process, a malicious node (Node M) broadcasts a tampered ID of the previous node, the current node or the next node. This is the same as case 2 in the RREQ process. The next hop of Node M, Node N, can detect it. In the data forwarding process, if the node along the route tampers ID_next, other nodes drop it since their IDs cannot match the ID_next embedded in the data forwarding packet. The sender can detect the tampered ID_next since every node records its next two hops. It blacklists the next hop as the malicious node and reports it to the source node.

3.1.2 Intermediate Node Drops Messages

In the route discovery, if a malicious node drops the RREQ packet, it blocks itself. The sink node can receive the RREQ packet through other routes. If the malicious node (Node M) drops the RREP packet, the next hop (Node N) can detect it since it cannot receive the packet again. In a data forwarding process, if a malicious node drops the data packet, the sender can detect it since it can not get acknowledgement from the next hop. It will inform it to the source node.

3.1.3 Intermediate Node Modifies Messages

In the route discovery, if a malicious node modifies the RREQ core content, such as ID_source, ID_sink, ID_RREQ, or N_source, the sink node can detect it through verifying the MAC. It drops the corrupted RREQ packet, and receives it from other routes. If a malicious node modifies the RREP core content, such as, or, the source node can detect it through the MAC. In the data forwarding, we use the same solution as the case of the modified RREQ core content through verifying the MAC. In the query dissemination in the whole sensor network, the intermediate nodes can be compromised as Fig. 3.

Figure 3.

Query dissemination.

The intermediate malicious node modifies the request query (reqQ) and broadcasts the changed request query (ChangedReqQ). The other sensor node receives the ChangedReqQ, and gets the query result which is packed up in the reply Query (replyQ). The query result contains the wrong information since the reqQ is tampered.

The sink node receives the replyQ, and gets the reqQ from the replyQ packet. Here, the reqQ actually is the ChangedReqQ. The sink node also can get the correct reqQ according to the Q_ID. Then, it compares the correct reqQ with ChangedReqQ. If they match, the sink node can trust the query result from the reply packet. Otherwise, it drops it.

3.1.4 Source Node is a Malicious Node

If the source node is a malicious node, it tries to send abnormal messages to the sink node. The sink node can detect this after it compares the data with the record in the history and the neighboring node's report. Then it sends the further request to the nodes in the cluster, and waits for the replies from these nodes for the further analysis.

3.2. Cost Analysis

This section gives the computational complexity, storage overhead, and energy consumption analysis through comparing ESecRout with AODV and SAODV protocols. We define N as the total number of sensor nodes.

3.2.1 Computational Complexity

In the ESecRout protocol, the source node sends the RREQ once to start the secure route discovery process, thus the computational cost is O(1). Each intermediate sensor node only accepts the first RREQ, then broadcasts it, thus the total cost is O(N-2). The cost that the sink node generates RREP is O(1). We assume that the total number of hops along the route between the source node and the sink node is N_H, then the cost that RREP is forwarded to the source node is O(N_H), which is O(1) since in general N_H ≪ N if the sensor nodes are deployed in a rectangular region (length × breadth), where length is not much different than breadth. The total computational cost for the secure route discovery in the ESecRout protocol is O(N). The computational cost for the route discovery in the AODV protocol is O(N). The computational cost for the route discovery in the SAODV protocol is O(N). Thus, ESecRout has the same computational complexity as of SAODV and AODV though it provides energy efficient security.

3.2.2 Storage Overhead

In the ESecRout protocol, all the nodes maintain a shared key with the sink node. Each node also needs to maintain its cluster key. We assume the key size is S_k bytes. The sensor node needs the additional key storage of 2S_k bytes. In addition, each cluster head maintains the IDs of its cluster members. Assume that the average member number of the cluster is N_C, and the size of the ID is S_ID bytes, then the cluster head needs the storage of ${N_{C}}^{*} S_{I D}$ bytes. The member of the cluster only needs to maintain the ID of its cluster head, which is S_ID. Moreover, each node maintains the routing table with the ID of the source node, and the IDs of its previous and next two hops, which is totally 5S_ID if there is only one route that exists. Assume that the average number of routes of a node is N_R, then the node needs the storage of $5 {S_{I D}}^{*} N_{R}$ bytes to maintain the routing table. In summary, the cluster head needs the storage of ( $2 S_{k} + {N_{C}}^{*} S_{I D} + 5 {S_{I D}}^{*} N_{R}$ ) bytes, and the cluster member totally needs the storage of ( $2 S_{k} + S_{I D} + 5 {S_{I D}}^{*} N_{R}$ ) bytes. If the key size S_k is 8 bytes [3], the size of ID S_ID is 4 bytes, the average member number of cluster N_C is 10, and the average number of routes N_R is 10, then the sensor node as the cluster head needs 256 bytes of storage, and the sensor node as a member of the cluster head needs 220 bytes of storage.

In the sensor network, the storage of a sensor node includes 4 KB of RAM for data, and 512 kB of flash memory [17]. The ESecRout only uses a small part of the memory and thus, it is suitable for use in the sensor network.

In the AODV protocol, each node needs the storage ( $3 {S_{I D}}^{*} N_{R}$ ) for its routing table. In the SAODV protocol, each node needs the storage of ( $2 {S_{I D}}^{*} N_{R}$ ) bytes for its routing table. In addition, each node needs to keep the public keys of other nodes. Assume that the key size for the public key is S_PK so each node needs the public key storage of N*S_PK. Therefore, in the SAODV, each node needs the total storage of ( $3 {S_{I D}}^{*} N_{R} + N^{*} S_{P K}$ ) bytes. If the key size S_PK is 128 bytes [18], the total number of sensor nodes N is 1000, the size of ID S_ID is 4 bytes, and the average number of routes N_R is 10, then the sensor node totally needs 125 KB storage. Thus, SAODV has much larger storage requirements than ESecRout and AODV.

3.2.3 Energy Consumption Overhead

The most energy consumption overhead during the route discovery includes the energy dissipation in the transmitting and receiving modes and the energy used for the complicated operations such as encryption, decryption, and hash function. If we use the first order radio model [19], to transmit a k-bit message for a distance d, the radio expends:

\begin{aligned} E_{T x} (k, d) = & E_{T x - e l e c} (k) + E_{T x - a m p} (k, d) \\ E_{T x} (k, d) & = E_{e l e c} * k + \in_{a m p} * k * d^{2} \end{aligned}

Where the radio dissipates E_elec = 50nj/bit to run the transmitter or receiver circuitry and ∊_amp = 100 pJ/bit/m² for the transmit amplifier. And, to receive this message, the radio expends:

E_{R x} (k) = E_{R x - e l e c} (k) = E_{e l e c} * k

The energy consumption overhead during the route discovery in the ESecRout protocol mainly includes the energy dissipation in the transmitting and receiving modes. More specifically, the energy is used to send and receive the RREQ, RREP, and error messages. The complicated operations such as encryption, decryption, and hash function in the ESecRout protocol are only involved in the source node and the sink node. Thus, it is negligible when comparing to the energy dissipation in the transmitting and receiving modes during the route discovery phase, which involved all the sensor nodes. Thus, the energy consumption overhead E_consp during the route discovery phase in the ESecRout protocol is:

\begin{aligned} E_{c o n s p} & = E_{T x} (k_{1}, d) + E_{R x} (k_{2}) \\ = E_{e l e c} * k_{1} + \in_{a m p} * k_{1} * d^{2} + E_{e l e c} * k_{2} \\ = (2 E_{e l e c} + \in_{a m p} * d^{2}) * k (i f k_{1} = k_{2} = k) \end{aligned}

where k₁ -bit message is transmitted and k₂ -bit message is received.

Therefore, the energy consumption in the ESecRout protocol is roughly proportional to the message byte overhead during the route discovery phase.

The energy consumption overhead during the route discovery in the SAODV protocol includes not only the energy dissipation in the transmitting and receiving modes, but also the complicated operations such as hash function. In the SAODV protocol [2], each node receiving a RREQ or a RREP message performs the following hash operation in order to verify the hop count:

T o p_H a s h == h^{M a x_H o p_C o u n t - H o p_C o u n t} (H a s h)

Where:

Max_Hop_Count is the maximum number of hops, which can be set as TimeToLive

Hop_Count is the number of hops from the source node

Hash can be originally set to the seed value, which is a random number

h is a hash function

Top_Hash = h^{Max_Hop_Count} (seed)

Then the node performs the following hash operation before it rebroadcasts a RREQ or forwards a RREP:

H a s h = h (H a s h)

Table 3 summarizes the energy cost of commonly used hashing algorithms [18].

Table 3
Energy Consumption of Hash Functions

Algorithm MD2 MD4 MD5 SHA SHA1 HMAC

Energy (μJ/B) 4.12 0.52 0.59 0.75 0.76 1.16

Algorithm	MD2	MD4	MD5	SHA	SHA1	HMAC
Energy (μJ/B)	4.12	0.52	0.59	0.75	0.76	1.16

Since the routing packet in the SAODV protocol is much bigger than the ESecRout protocol, the SAODV costs much more energy on transmitting and receiving routing packets than the ESecRout protocol. Moreover, each intermediate node in the SAODV protocol needs to perform the hash function for the hop count verification, which costs additional energy. This has also been verified in the next section during the experimental evaluation.

The energy consumption overhead during the route discovery in the AODV protocol mainly includes the energy dissipation in the transmitting and receiving modes. Since the routing packet in the AODV protocol is a little smaller than the ESecRout protocol, the AODV costs a little less energy on transmitting and receiving routing packets than the ESecRout protocol.

4. Performance Evaluation

We use the NS2 [20] to evaluate the performance of the ESecRout. In our simulation study, we use one source-destination pair. The source node sends a Constant Bit Rate (CBR) flow of 20 data packets per second. Each data packet contains 30 byte payloads [3]. We measure the performance using the following metrics [10]:

Byte Overhead: The total number of overhead bytes transmitted.

Energy Consumption: The total battery power loss.

Packet Delivery Ratio: The total number of packets received is divided by the total number of application—level packets originated.

Packet Latency: The elapsed time between the application layer passing a packet to the routing layer and that packet first being received at the destination.

The route discovery byte overhead for ESecRout, AODV and SAODV is shown in Fig. 4. From Fig. 4, we observe that the ESecRout protocol needs a little more route discovery overhead (about 8%) than AODV, but it is much less than SAODV which involves much more route discovery overhead than AODV (about 33%). This is because ESecRout has the additional security parameters embedded in the routing packets than AODV. ESecRout uses only symmetric cryptography with lower byte overhead than SAODV which uses asymmetric cryptography and hash chain.

Figure 4.

Byte overhead.

The route discovery energy consumption for ESecRout, AODV, and SAODV is shown in Fig. 5. From Fig. 5, we observe that the ESecRout protocol consumes a little more route discovery energy (about 8%) than AODV, but it is much less than SAODV which consumes much more route discovery energy than AODV (about 35%). This is because the routing packets for ESecRout are a little bigger than AODV, but are much smaller than SAODV. In addition, the ESecRout uses only symmetric cryptography, but SAODV uses the asymmetric cryptography. Moreover, in the SAODV, the intermediate nodes need additional energy for the hash calculation during the route discovery.

Figure 5.

Energy consumption.

The packet delivery ratios for ESecRout, AODV, and SAODV are shown in Fig. 6. Three sessions based on the simulation time are performed: session 1 is 10 seconds, session 2 is 50 seconds, and session 3 is 200 seconds. From Fig. 6, we observe that the packet delivery ratios for ESecRout, AODV, and SAODV are very close. The packet delivery ratios are above 98% in all the cases. But session 1 has the lowest packet delivery ratio, and session 3 has the highest packet ratio. This is because the data packet is not delivered during the route discovery phase. Session 1 has the lowest time to send the data packets after the route discovery, but session 3 has the highest time to send the data packets. Therefore, session 1 has the lowest average packet delivery ratio, and session 3 has the highest average packet delivery ratio.

Figure 6.

Packet delivery ratio.

Packet latency for ESecRout, AODV and SAODV is shown in Fig. 7. Three sessions based on the simulation time are performed: session 1 is 10 seconds, session 2 is 50 seconds and session 3 is 200 seconds. From Fig. 7, we observe that the packet latency for ESecRout, AODV, and SAODV is very close. The average packet latency is between 14 ms and 16 ms. But session 1 has the highest packet latency, and session 3 has the lowest packet latency. This is because the data packet is not delivered until the route discovery phase ends, which results in the biggest packet latency during the route discovery phase. The time on sending data packets becomes more from session 1 to session 3. Therefore, the average packet latency becomes lower from session 1 to session 3.

Figure 7.

Packet latency.

Thus, the last two experiments show that though our protocol provides energy efficient security against attacks, it does not decrease the packet delivery ratio and increase the packet latency when compared with AODV and SAODV protocols.

5. Related Work

Perkins and Royer [1] proposed the AODV protocol, which is an on-demand variation of the distance vector routing protocol. When a source node desires to send a message to the sink node and it does not have the valid route, it initiates a route discovery process. The source node sends the RREQ to its neighbors, who forward it to their neighbors until it reaches the sink node if the intermediate does not have the route, and the sink node sends the RREP. Otherwise, the intermediate node sends the RREP if it has the route. The source node receiving the RREP builds the route to the sink node. Zapata and Asokan [2] proposed the SAODV protocol, which is used to protect the routing messages of the original AODV. SAODV uses digital signatures to authenticate non-mutable fields and hash chains to authenticate the hop-count field in both RREQ and RREP messages. Perrig et al. [3] presented two security protocols, SNEP and μTESLA, for sensor networks using symmetric schemes. This paper only considers peer to peer architecture, and has not considered the sensor network as a hierarchical structure. Failure of the nodes has not been considered in this paper. Yi et al. [21] proposed a security-aware routing protocol (SAR) for wireless ad hoc networks. In this protocol, every node is set by one security level. The routing packet with the security parameters will make routing decisions according to the security parameters and the security level of the node. Papadimitratos and Haas [13] proposed a secure routing protocol (SRP) in MANET. The route request packet is composed of the SRP header in addition to the basic routing protocol packet and IP header. This routing discovery protocol can provide the correct connectivity information despite some compromised nodes in ad hoc networks. Hu et al. [10] proposed a secure efficient ad hoc distance vector routing protocol (SEAD) based on the design of the destination-Sequenced Distance-Vector routing protocol (DSDV). In this protocol, efficient one-way hash functions are used.

6. Conclusions

In this paper, we presented an energy efficient secure routing protocol for sensor networks (ESecRout). The ESecRout guarantees that the sink node gets the correct query result from the sensor network. In ESecRout protocol, only high efficient symmetric cryptography is used. The two-level architecture is used for a lower message overhead. The different types of attacks which may present in sensor networks are analyzed in the security analysis section. We argued there that ESecRout protocol is robust in the presence of such attacks. The cost analysis shows that the ESecRout protocol is an energy efficient secure routing protocol in comparison with SAODV and AODV. The simulation results verifies the analytical results and show that the ESecRout protocol performs much better than SAODV [2] with much less route discovery byte overhead and much less energy consumption during the route discovery phase keeping the same packet latency and delivery ratio as in SAODV.

References

Perkins

C. E.

and Royer

E. M.

, “Ad hoc On-Demand Distance Vector Routing”, In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, Feb 1999, pp. 90–100.

Zapata

and Asokan

, “Securing Ad-hoc Routing Protocols”, In Proceedings of ACM Workshop on Wireless Security (WiSe), Atlanta, GA, Sept. 2002.

Perrig

Szewczyk

Wen

Culler

, and Tygar

J. D.

, “SPINS: Security Protocols For Sensor Networks”, In Proceedings of Mobicom, 2001.

Karlof

and Wagner

, “Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures”, First IEEE International Workshop on Sensor Network Protocols and Application, May 2003.

Zhu

Setia

, and Jajodia

, “LEAP: Efficient Security Mechanisms for Large-Scale Distributed Sensor Networks”, In Proceedings of 10th ACM Conference on Computer and Communications Security (CCS '03), Washington D.C., October, 2003.

Ning

and Sun

, “How to Misuse AODV: A Case Study of Insider Attacks against Mobile Ad-hoc Routing Protocols”, Proceedings of the 2003 IEEE Workshop on Information Assurance United States Military Academy, West Point, NY June 2003.

Carman

D. W.

Kruus

P. S.

, and Matt

B. J.

, “Constraints and approaches for distributed sensor network security”, NAI Labs Technical Report #00–010, September 2000.

Zapata

M. G.

, “Secure Ad hoc On-demand Distance Vector Routing”, ACM SIGMOBILE Mobile Computing and Communications Review, Volume 6, Issue 3, July 2002.

Tubaishat

Yin

Panja

, and Madria

, “A Secure Hierarchical Model for Sensor Network”, ACM SIGMOD Record, Vol. 33, No. 1, March, 2004.

10.

Yih-Chun

Johnson

David B.

, and Perrig

Adrian

, “SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks”, Fourth IEEE Workshop on Mobile Computing Systems and Applications, WMCSA'02.

11.

Yin

Jian

Madria

Sanjay

, “SecRout: A Secure Routing Protocol for Sensor Networks,” aina, pp. 393–398, 20th International Conference on Advanced Information Networking and Applications – Volume 1 (AINA'06), 2006.

12.

Deb

Budhaditya

Bhatnagar

Sudeept

and Nath

Badri

, “A Topology Discovery Algorithm for Sensor Networks with Applications to Network Management”, In IEEE CAS Workshop, September 2002.

13.

Papadimitratos

and Haas

Z. J.

, “Secure Routing for Mobile Ad Hoc Networks”, SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), San Antonio, TX, January 27–31, 2002.

14.

Krawczyk

Bellare

, and Canetti

, “HMAC: Keyed-Hashing for Message Authentication”, RFC 2104, February 1997.

15.

Rivest

R. L.

, “The RC5 Encryption Algorithm”, Proc. 1^st Workshop on Fast Software Encryption, pages 86–96, 1995.

16.

Lin

Yuxia

Hamed

Amir

Rad

Mohsenian

Wong

Vincent W. S.

, and Song

Joo-Han

, “Experimental Comparisons between SAODV and AODV Routing Protocols”, in Proceedings. of 1st ACM Workshop on Wireless Multimedia Networking and Performance Modeling (WMuNeP), Montreal, Quebec, pp. 113–122, Oct. 2005.

17.

Karlof

Sastry

, and Wagner

, “TinySec: A Link Layer Security Architecture for Wireless Sensor Networks”, In Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys 2004), Baltimore, Maryland, November 2004.

18.

Potlapally

N. R.

Ravi

Raghunathan

, and Jha

N. K.

, “Analyzing the Energy Consumption of Security Protocols”, In Proceeding of the 2003 International Symposium on Low Power Electronics and Design (ISLPED'03), pp. 30–35, Seoul, Korea, 2003.

19.

Heinzelman

Chandrakasan

, and Balakrishnan

, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks”, In Proceedings of the Hawaii Conference on System Sciences, Jan. 2000.

20.

NS2 web site, http://www.isi.edu/nsnam/ns

21.

Seung

Naldurg

Prasad

, and Kravets

Robin

, “A Security-Aware Routing Protocol for Wireless Ad Hoc Networks”, Poster presentation, ACM Symposium on Mobile Ad Hoc Networking & Computing (Mobihoc 2001), Long Beach, California, October, 2001.