# An Enhanced Communication Protocol for Location Privacy in WSN

Authors: Abdel-Shakour Abuzneid; Tarek Sobh; Miad Faezipour
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Wireless sensor network (WSN) is built of many sensor nodes. The sensors can sense a phenomenon, which will be represented in a form of data and sent to an aggregator for further processing. WSN is used in many applications, such as object tracking and security monitoring. The objects in many situations need physical and location protection. In addition to the source location privacy, sink location privacy should be provided. Providing an efficient location privacy solution would be challenging due to the open nature of the WSN. Anonymity is a key solution for location privacy. We present a network model that is protected against local, multilocal, and global adversaries that can launch sophisticated passive and active attacks against the WSN.


---

## Body

## 1. Introduction

A wireless sensor node (SN) is a simple autonomous host device. It can sense a phenomenon, convert the sensed information into data, process the data, and then transmit the data to a base station (BS) for further analysis. The SN host is very limited in terms of storage space, memory, processing power, communication bandwidth, and battery energy [1]. This work focuses on monitoring and tracking applications, such as tracking animal in the wildlife or a fellow soldier in the battlefield. When the SN senses an object, it reports data by sending it hop-by-hop to the BS. One of the most common applications discussed in the literature is thepanda monitoring game [1]. When a sensor node detects a Panda in a certain area, it should report the data via a message to the BS. The fact that the data is sent out of the SN in open environment will be a reason for the adversary (ADV) to know the location of the SN and consequently the location of the object. In order to protect the Panda from the ADV, we need to implement in place an efficient source location privacy scheme (SLP). SLP is even more important in military, homeland security, and law enforcement, in addition to many civilian applications [2]. We need, as well, to provide location privacy for the BS (BSLP), which is the data aggregator and the controller of the WSN. The solution needs to provide anonymity where the ADV cannot know the identity of the SNs. We have to reduce the capture likelihood and increase safety period. Safety period is the time before the first SN is captured. All transmissions in the WSN happen in the open air where the SNs are unattended. One of the most important issues that any solution needs to account for is the energy conservation to maintain a longer life for the WSN. Thus, applying regular privacy and security algorithms might not be suitable for such networks.


## 2. Problem Statement

Privacy in WSN is typically categorized into two categories: data privacy and context privacy [3]. Data privacy focuses on data aggregation and data query. Contextual privacy involves location privacy, identity privacy, routing privacy, and temporal privacy. Providing SLP and BSLP could be achieved using many schemes such asrandom walk, geographic routing, delay, dummy data sources, cyclic entrapment, anonymization, cross-layer routing, separate path routing, network coding, and other schemes[1, 4].In this work, we will useanonymization to provide SLP and BSLP. One of the first works to classify context privacy was done by Kamat et al. [5, 6], where they addressed the Panda hunter game. They claim that the routing scheme is responsible for hiding source location of an object. They have used two metrics to measure SLP: first, thesafety period, which is the number of messages a source sends before it is captured, and second, thecapture likelihood, which is the probability that an adversary can capture the source within a certain period. There are generally two ways to locate a source using passive attacks:traffic analysis [3, 7] andpacket tracing [3, 8, 9]. We provide a framework that can be tested against other solutions using five metrics:security: the probability that the adversary successfully identifies the source, the intermediary SNs, or the BS;energy cost, where the solution will provide privacy with reasonable energy conservation;storage memory cost anddelivery time, where the solution should consume a reasonable storage space and provide reasonable delays;safety period, where the solution will guarantee transmission of reasonable amount of messages before the first SN is captured. The rest of this paper is organized as follows. In Section 3, we give some background and literature survey. In Section 4, we will explain the suggested system model, network model, threat model, and the traffic model. In Section 5, we will introduce our anonymity protocol. In Section 6, we will have a thorough security analysis. In Section 7, we will have performance analysis and evaluation. In Section 8, we will summarize our work and suggest some additional models to the framework in the future work.


## 3. Background and Literature Survey

There are many solutions, which have been presented to solve the problems of SLP and BSLP. Conti et al. [1] categorized the solutions into groups. They have discussed many solutions and compared them in terms of the threat model, view of the network, power consumption, exposed information, and efficiency in providing “location privacy.” Recently, anonymity has become a concern for WSNs. We have identified important literature discussing solutions for anonymity in WSN, such as HIR: Hashing-Based ID Randomization [10]; RHIR: Reverse HIR [10]; SAS: Simple Anonymity Scheme [11]; CAS: Cryptographic Anonymity Scheme [11]; MAQ: Max Query Aggregation [12]; APR: Anonymous Path Routing [13]; ACS: Anonymous Communications Scheme [14]; DCARPS: Destination Controlled Anonymous Routing Protocol for Sensor Nets [2]; PhID: Phantom ID [15]. None of these solutions provides location privacy against global ADVs and active attacks. A reasonable solution against global adversary introduced by Chen et al. [16] called efficient anonymous communication (EAC), which provides sender, link, and sink anonymity. The solution consists of three phases. Every SN creates multiple pseudonym IDs, which are global anonymous identity, anonymous broadcast identity, and anonymous one-hop identity, and anonymous acknowledgement identity. Each transmission should have a new anonymous pseudonym. The solution is relatively light; however, it easily breaks pseudonym synchronization. In addition, it fails to provide BSLP and it is not secure against traffic rate analysis attacks. We know thatanonymization is not enough to achieve end-to-end privacy. There are some solutions based on dummy data sources where SNs send out fake packets to other nodes within the network. A fake packet does not contain any information about any real event but it helps to obfuscate the real traffic and to divert the adversary. The literature shows reasonable solutions using dummy sources. Some of them are designed to handle local ADV. However, few are suitable for global ADV. Some of the literatures presume a certain routing scheme, topology, network, and threat models. Ouyang et al. [17] introduced three different solutions to handle the global ADVs. In this work, we will enhance EAC, the efficient anonymous communicating protocol [16, 18]. EAC does not handle the pseudonyms synchronization very well. There are many situations where the system will get unsynchronized. It also could not handle multi-colluding adversaries and lacks a mechanism for time correlation attack. There is an extension for EAC presented in [4] which has reasonably addressed some of the issues of EAC. Most of the other solutions do not handle global or multi-colluding adversaries. Each solution focuses on certain scenarios of attacks. Our work is aimed to be comprehensive.


## 4. Preliminaries

Our contribution in this work provides sender anonymity, receiver anonymity, link anonymity, SLP, BSLP, and data privacy. The system is fed with inputs, such as the nature of the ADVs in the network and the residual energy in the SNs. We assume bidirectional links where two nodes are considered neighbors if they can hear each other [2]. The network considers one BS which aggregates sensed data from all the SNs. The BS works as an interface to the wired network [11]. Data packets generated by SNs are addressed to the BS; however, they go through multihop paths. Control packets are sent from the BS to the SNs by unicast or broadcast messages. To enhance BSLP, the BS acts like a normal SN in the network when it communicates with other SNs, to make it indistinguishable. The WSN runs in two phases: startup phase and communication phase. We assume that the SNs have the ability to obfuscate the addresses at the MAC level header [11]. All sensors are time synchronized [11]. There are many algorithms for SNstime synchronization, which is out of the scope of this work. The WSN will need a protocol fornetwork topology discovery that allows the BS to view the global topology of the network without revealing the BS location [2]. The adversary nodes have very strong capabilities compared to the SNs. They are resource-rich; they have sufficient energy supply, computation capabilities, and unlimited storage memory. An adversary could run bothpassive andactive attacks. We presume that only few compromised nodes could exist at one time due to the implementation of intrusion detection system (IDS) which is able to detect compromised SNs. We assume a global adversary, which can monitor the traffic of the entire network and can determine the node responsible for the initial transmission. Assuming a global adversary means the following: (a) the worst-case scenario for area coverage where colluding sensors can cooperate to cover the whole network area [21]; (b) the worst-case scenario for timing where the coverage area of the adversary is not known at any time [21]. We also assume that the adversary is capable of observing SNs transmissions over extended periods. It is, however, not able to break the encryption algorithms or the hash functions used for securing data during transmission. We presumeabundant traffic where sensors detect and transmit many packets, such as in the applications of environment monitoring.


## 5. Proposed Anonymous Model

The communication process is divided intotwo phases, namely: startup phase and communication phase.


### 5.1. Startup Phase

Prior to actual distribution of the sensors in the field of application, the SNs need to be tested, fully charged, and preloaded with some parameters which are needed during the startup phase and then during the communication phase. All parameters and terms used for the proposed solution are mentioned in Notations [4, 16, 19].It is typical to presume that the WSN is considered secure for some short period after SNs’ deployment in the field and before the steady communication phase. Zhu et al. [22] presented that WSN has a lower bound on the time interval that the adversary needs to be able to compromise a SN. During this time, the SNs can communicate and exchange all preloaded and calculated parameters safely. The SNs need to know their relative locations to the BS and to the neighboring SNs. Likewise, the BS needs to know the location of all the SNs participating in the WSN. There are Nemourslocalization schemes which are proposed in the literature [11, 16, 23, 24]. After the localization process is completed, each SN will know its smallesthop-count to the BS (hci↔bs).


#### 5.1.1. Issuing the Pseudonyms

A SN uses any issued pseudonym only once. That means we need to use a one disposable pseudonym per a transmission. There are five kinds of transmissions that could happen in the WSN [4, 16]: (i) multihop transmission between a SN and BS, (ii) transmission between two neighbor SNs, (iii) broadcast sent by a SN or the BS, (iv) acknowledgement, and (v) fake broadcast. The process starts by creating a pseudonym ID for each SNi, and we call it for short (PIDi) which is issued using the following expression:(1)PIDi=HIDi⊕ai.The SNi can calculate the broadcast pseudonym ID (BPIDi) according to the following expression:(2)BPIDi=HIDi⊕bi.The SNi can calculate the fake broadcast pseudonym ID (FBPIDi) according to the following expression:(3)FBPIDi=HIDi⊕ci.SNi should know its entire neighbor set Ni. A neighbor SNj is a sensor that could receive signal from the SNi and vice versa through one-hop transmission. SNi will send Mdiscovery, a broadcast discovery message, to exchange parameters with all one-hop neighbors. The format of the message is as follows:(4)Mdiscovery=kdis·TTL∥IDi∥ki↔bs∥kbi∥fkbi∥ai∥bi∥ci∥HCi↔bs.The value of TTL should beone for this transmission. SNi will receive also a similar broadcast message from SNj and from all other neighbors. Both SNi and SNj will calculate a new random value (ai↔j) according to the following expression:(5)ai↔j=HIDi⊕IDj.Both SNi and SNj will calculate also a new pairwise key ki↔j according to the following expression:(6)ki↔j=Hki↔bs⊕kj↔bs.SNi also calculates broadcast pseudonym ID for SNj (BPIDj) according to expression (2). SNi has already received the values of IDj and bj through Mdiscovery. It also calculates the one-hop pseudonym ID (OHPIDi↔j) shared between SNi and SNj as expressed in the following expression:(7)OHPIDi↔j=Hai⊕aj.Finally, acknowledgement pseudonym ID for SNi (APIDi) will be calculated according to the expression below:(8)APIDi=HIDi.SNi will have a table TBLi which contains the shared values with the neighbors as listed in Table 1. Thus, we have replaced the ID withquintuple pseudonyms [4] to reference the SN during the communication. Figure 1 shows two sensors after they have exchanged the required pseudonyms.Table 1
Shared values among sensor neighbors. IfSNi has Ni neighbors, then TBLi will have N tuples, one tuple per a neighbor [4, 16].
Information inTi per each neighbor
Tuple forSNj
Shared random number
a
i
↔
j
Shared broadcast random number
b
j
Shared fake broadcast random number
c
j
Shared broadcast key
BPID
j
Shared fake broadcast key
FPID
j
Shared one-hop key
k
i
↔
j
Current one-hop pseudonym ID
OHPID
i
↔
j
Link direction
link
i
→
j
Residual energy level
Δ
jFigure 1
Two SN neighbors share the required pseudonyms.


#### 5.1.2. Deleting Security Information

After storing all required pseudonyms, parameters, and keys inTBLi for SNi, it would be the time to delete all unnecessary information for the purpose of security [4, 16, 25]. In addition, it will release some memory storage space [16, 18]. Most importantly, SNi will delete IDi and HCi↔bs, which could be critical information for the adversary. In addition, SNi will delete discovery messages received earlier from the neighbors.


### 5.2. Communication Phase

During the steady communication phase, when sensing and sending data by nodes to the BS takes place,seven operations continue until the network lifetime ends. These operations are [4] (i) sensing and sending a message to a neighbor, (ii) forwarding a message to a neighbor, (iii) broadcasting a message, (iv) acknowledgement, (v) sending a fake message, (vi) SN addition, and (vii) SN removal. A SN will have three roles, in terms of data transmission, during the communication phase [4, 16, 25]: (i) role as a sensor, (ii) as a forwarder or intermediary node, and (iii) as a broadcaster. In the following sections, we will use SNi as a source node and SNj as a neighbor to the source.


#### 5.2.1. Transmission as a Sensor

WhenSNi senses data, it needs to send a message hop-by-hop to the BS. The SNi only recognizes itself by its newly calculated pseudonym (PIDi), and the BS will recognize source of the message through PIDi identity as well. Thus, the PIDi of the source needs to be included in the message until it reaches the BS. Consequently, the PID of a sensor will be updated after every transmission. When data is sensed and ready to be sent out, the SNi needs to select one neighbor from Ni to forward the message to it. The selection process goes through a probabilistic protocol which guarantees that SNi does not depend all the time on one neighbor when forwarding its data; first, for routing privacy and second for increasing the lifetime of the WSN. SNi will form the message in the following format:(9)Mi→j=OHPIDi↔j∥Eki→j·PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.Once SNi knows that the message (Mi→j) is delivered to the BS, it needs to dispose of the current pseudonym PIDi and issue a new one for the next transmission as indicated in the following expression:(10)PIDi=HPIDi⊕ai.In addition, both SNi and SNj will dispose of the current OHPIDi→j and issue a new one for the next communication between the two sensors according to following expression:(11)OHPIDi→j=HOHPIDi→j⊕ai→j.The message M will then be reformatted by the recipient SNj. Then, it will be forwarded to the next node, in the path, SNr, and so on, until it gets to the BS. If SNj was the BS, then the BS uses the shared one-hop key between the sensor and the BS to decrypt the encrypted data and gets the PIDi, which the BS can use to recognize the SNi. Thus, the BS will be able to recognize the originator of this message. Only at this point of time, BS can update the value of PIDi of SNi. It also gets the data (Di) which BS can read after decrypting the data by ki↔bs.


#### 5.2.2. Transmission as a Forwarder

WhenSNi sends the message one-hop uplink to the neighbor SNj, SNj needs to forward the message to another intermediary node or in the best case to the BS if SNj is a neighbor of the BS. Upon receiving Mi→j, SNj will match OHPIDi→j in its table, Tj, under the column related to SNi. If there is no match, then the message definitely is not addressed for SNj and it will be dropped immediately. If it matches, then the message is addressed to SNj and it will be decrypt using ki→j. The message will be forwarded to SNr after M is reformatted as in(12)Mj→r=OHPIDj↔r∥Ekj→r·PIDi∥Eki↔bsDi∥HMACki↔bsPIDi∥Di.Right after the data isreceived by SNj andforwarded to the next one-hop SNr, the SNj updates both pseudonyms, OHPIDi↔j and OHPIDj↔r. SNj now is ready to exchange another message with SNi using the new pseudonym OHPIDi↔j. However, SNj is not yet ready to send data to SNr since SNr does not update the OHPIDj↔r until Di is forwarded to the next hop, say NSv. What would happen if SNj senses new data while it is busy forwarding a previous message? It has to wait until OHPIDj↔r is updated or it can use a different neighbor to forward the new message.


#### 5.2.3. Acknowledgment

As expected in data networks, message could be lost or become corrupted. In either case, retransmission is required. Because SNs change PIDs after each transmission, synchronizing PIDs is crucial. Updating the pseudonyms depends on successful message transmission and reception. Technically, a sender and a receiver should alter the pseudonym value only after making sure that the data are sent correctly and received perfectly by the BS. The lack of direct connection between the sender and the receiver makes it a complicated process. The BS cannot send direct acknowledgement to the source if it is multiple hops away. We have to depend on multiple acknowledgements along the path between the source and the destination. Transmitting data through a route ofy hops needs y acknowledgements. SNi needs to calculate acknowledgement pseudonym ID (APIDi) according to the following expression:(13)APIDi=HAPIDi⊕bi.The message will be sent out now with the current value for APIDi. Thus, we will rewrite Mi→j as it appears in(14)Mi→j=Padding∥OHPIDi↔j∥Eki→j·APIDi∥PIDi∥Eki↔bs(Di)∥HMACki↔bs·PIDi∥Di.Padding is added to make sure all the one-hop packets have the same size to prevent ADV from identifying the source bytraffic analysisandsize correlation attacks. When SNj receives the packet, it will reformat the packet as in expression (15) and then will send it to SNr:(15)Mj→r=APIDi∥OHPIDj↔r∥Ej→r·APIDj∥PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.The transmission of Mj→r should be heard by all the neighbors including both SNi and SNr. If SNi hears the message and reads APIDi, the SNi knows that Mi→j was received correctly by SNj. Only at this time, SNi updates the value of OHPIDi↔j. PIDi will be updated, as well, since SNi is the source of the message. Here are two scenarios.Scenario 1.
The packet sent bySNi is lost or got corrupted. In this scenario, SNj considers nothing happened, so it will not forward any message onward. Meanwhile, SNi will wait for ζ time to expire. It will send the message again with updated APIDi. Once the message is acknowledged according to the procedure explained earlier and if the SN is the source, then PIDi, OHPIDi, and APIDi will be updated and be ready for a new packet to be sent out. If it is intermediary SN, only OHPIDi and APIDi are updated.Scenario 2.
The packet is received correctly bySNj, the new packet Mj→r is sent out including the acknowledgement APIDi, and SNj updated the value of OHPIDi↔j. However, SNi does not hear the forwarded message Mj→r within time ζ. At this moment, SNi does not know for sure if the packet was delivered or the acknowledgement is lost. It has to account for the worst-case scenario. A copy of the message will be retransmitted to SNj with the current OHPIDi and updated APIDi. SNj can recognize the message because of the value of old OHPIDi. After receiving theretransmitted packet, it now sends direct acknowledgement to SNi as in the following expression:(16)ACKi←j=APIDi∥Padding.BS is treated similar to normal SN, so it has to acknowledge every packet it receives. After the packet is delivered to the BS, and after the message is acknowledged, the PIDi (of the source) will be updated. Both the SNi and the BS will be ready to exchange a new message. As long as the new message does not reach the BS before the old PIDi is updated, the system will continue to be synchronized. This way, we have a possible window of one message. However, there is no guarantee to have all messages arrive in order. The only way to do it is if the system accounts for minimum interval time ωmin⁡, which is the minimum time span between two messages. However, in some cases, the packet cannot be delivered at all through a certain route. One obvious scenario is when an intermediate node is depleted out of energy before it forwards the message onward. The message needs to be rerouted through a different intermediate node which could cause a sever delay. We suggest implementing a sliding window mechanism as exhibited in Figure 2. For each sensor, we can have a window of W size. If we have k bits for the sequence number of the PID, then we can have a sliding window of 2k-1 slots. Once the BS finds out that the sequence of PIDs is not synchronized, it will send a message to resynchronize the sensor with the BS.Figure 2
Sliding window for received PIDs [19].


#### 5.2.4. Transmission as a Broadcaster

Typically, the BS is required to broadcast messages for control and management purposes. Likewise, a sensor might need to broadcast a message to the BS for network setup, maintenance, and other management issues. A sensor, as well, could broadcast a message for emergency or urgency reasons depending on the application at hand. The framework requires keeping all the packets, transmitted throughout the network, indistinguishable by the adversary. Thus, all the messages need to have the samesize. Broadcast isone-to-many transmission; a SNi can broadcast a message to all the neighbors in the set Ni. Each SN is preloaded with a broadcast key (kbi) and assigned broadcast pseudonym ID (BPIDi). The broadcast message sent by SNi is formatted as in the following expression:(17)Mb=Padding∥BPIDi∥EkbiDb.The broadcast message from a source SNi will be received by all the neighbors ∈Ni. SNi and the recipients will update BPIDi according to the following expression: (18)BPIDi=H1BPIDi⊕bi.Upon receiving the broadcast message (Mb), SNj decrypts the message using the stored key (kbi) in the table TBLj. It then encrypts it again using kbj and broadcasts Mb to its one-hop neighbors set (Nj) as in the following expression:(19)Mb=BPIDi∥BPIDj∥EkbjDb.When the BS receives a broadcast message, it is ultimately the destination, so intuitively it does not need to broadcast the message again. Our proposed framework assumes that the BS behaves like a normal sensor. To maintain this precourse, we require the BS to broadcast the message again. Thus, we introduce the limited broadcast where the BS will broadcast only to one hop with TTL = 1. Likewise, to reduce the unnecessary traffic, we have required the intermediary nodes to rebroadcast only to the neighbors with smaller HC in case of uplink messages and to neighbors with bigger HC in case of downlink messages. What if the neighbors, with less HC, are all dead? We could end up with a section completely disconnected from the BS. The protocol needs to consider broadcast messages to all the neighbors in this case.


#### 5.2.5. Limited Broadcast Messages

A sensor inside network maze can only recognize the neighbor sensors and the BS. When SN broadcasts a message uplink, then all sensor neighbors should hear it. When intermediary sensor gets broadcast message, it should rebroadcast the message if and only if the message is received from SN with bigger HC. This way the message is directed to the BS through multiple routes while saving unnecessary traffic. TheTTL=HCmax⁡ where HCmax⁡ preloaded at the startup phase. The value will keep reduced by one until it gets to the BS. In case of the downlink messages from the BS to all the sensors, the intermediary sensor would rebroadcast the message if and only if it is coming from a SN with smaller HC. In this case the message will hold TTL = 0 without change as an indication of BS as the source until it reaches all the sensors. The special case of broadcast is when TTL = 1 where the message will be broadcasted to one hop only.


#### 5.2.6. Fake Broadcast Message

The sensors need to send fake messages to preventtime correlation attack and statistical analysis. The rate of the fake messages follows a certain protocol. Fake message is a one-hop broadcast message. However, to prevent correlation, the message needs to behave similar to real messages. Therefore, the message needs to be encrypted and has similar size as real messages. This will make the fake messages indistinguishable from the real messages. Since it has to carry a dummy data, we chose to make it carryresidual energy(Δ) of the source sensor. This information will be extracted by the recipient neighbors and saved in the related tuple in the table TBL. The fake broadcast message sent by SNi is explained in the following expression:(20)Mf=Padding∥FPIDi∥EkfiΔi.The fake broadcast message from SNi will be received by all the neighbors, for example, SNj, SNu, SNv∈Ni. SNi and the recipients will then update FPIDi according to expression (21)FPIDi=H1FPIDi⊕ci.There is no need to worry about the pseudonym synchronization since the main purpose of fake message is to show activity in idle sensors to obfuscate real messages.


### 5.3. SN Removal

There are many reasons why we need to remove a sensor from the network. For instance, when the battery of the sensor is about to deplete, it should refrain from participating in transmission in preparation of removing it from the network. This would protect against lost data and keep the pseudonyms synchronized.In some cases, WSN uses intrusion detection system (IDS) [26], to protect against active attacks. Once SN is captured by the ADV, SN must be removed from the network and banned from participation in data transmission. Procedurally, if SNi opts to be removed, it sends two messages requesting the removal. The first message is to the BS as in expression(22)Mi→j=OHPIDi↔j∥Eki→jPIDi∥Eki↔bsDremove.The tuple of the SNi in the BS tables will be disabled permanently. The SNi will send a broadcast message to the neighbors according to(23)Mb=Padding∥BPIDi∥EkbiDremove.Once the neighbors get the message Dremove, they will delete the tuple related to SNi from the tables. Neighbors will refrain from exchanging messages with SNi. The same process could be established by the BS to remove a captured SN from the network.


### 5.4. SN Addition

To addSNi to the network, it will be preloaded with all setup parameters: IDu, au, bu, cu, H1, ku↔bs, and kbu, and fkbu. Right after deployment, SNi calculates the shared parameters with its neighbors. The BS should be trusted to run the process. Before sharing the calculated parameters with the SNi, the neighbors authenticate the new sensor. The BS will send special key kadd to all the nodes by a broadcast message. SNi will be preloaded with the same key as well. SNi and the neighbors will use this special key to authenticate with each other. Initially, the BS sends the following broadcast message to all of its one-hop neighbors as in the following expression(24)Mb=Padding∥BPIDbs∥Ekb-bsDadd,where Dadd is expressed in expression(25)Dadd=hc∥kadd.The initial value for hc is 0 where it represents the hop count. It will be incremented every time the message is forwarded.


## 5.1. Startup Phase

Prior to actual distribution of the sensors in the field of application, the SNs need to be tested, fully charged, and preloaded with some parameters which are needed during the startup phase and then during the communication phase. All parameters and terms used for the proposed solution are mentioned in Notations [4, 16, 19].It is typical to presume that the WSN is considered secure for some short period after SNs’ deployment in the field and before the steady communication phase. Zhu et al. [22] presented that WSN has a lower bound on the time interval that the adversary needs to be able to compromise a SN. During this time, the SNs can communicate and exchange all preloaded and calculated parameters safely. The SNs need to know their relative locations to the BS and to the neighboring SNs. Likewise, the BS needs to know the location of all the SNs participating in the WSN. There are Nemourslocalization schemes which are proposed in the literature [11, 16, 23, 24]. After the localization process is completed, each SN will know its smallesthop-count to the BS (hci↔bs).


### 5.1.1. Issuing the Pseudonyms

A SN uses any issued pseudonym only once. That means we need to use a one disposable pseudonym per a transmission. There are five kinds of transmissions that could happen in the WSN [4, 16]: (i) multihop transmission between a SN and BS, (ii) transmission between two neighbor SNs, (iii) broadcast sent by a SN or the BS, (iv) acknowledgement, and (v) fake broadcast. The process starts by creating a pseudonym ID for each SNi, and we call it for short (PIDi) which is issued using the following expression:(1)PIDi=HIDi⊕ai.The SNi can calculate the broadcast pseudonym ID (BPIDi) according to the following expression:(2)BPIDi=HIDi⊕bi.The SNi can calculate the fake broadcast pseudonym ID (FBPIDi) according to the following expression:(3)FBPIDi=HIDi⊕ci.SNi should know its entire neighbor set Ni. A neighbor SNj is a sensor that could receive signal from the SNi and vice versa through one-hop transmission. SNi will send Mdiscovery, a broadcast discovery message, to exchange parameters with all one-hop neighbors. The format of the message is as follows:(4)Mdiscovery=kdis·TTL∥IDi∥ki↔bs∥kbi∥fkbi∥ai∥bi∥ci∥HCi↔bs.The value of TTL should beone for this transmission. SNi will receive also a similar broadcast message from SNj and from all other neighbors. Both SNi and SNj will calculate a new random value (ai↔j) according to the following expression:(5)ai↔j=HIDi⊕IDj.Both SNi and SNj will calculate also a new pairwise key ki↔j according to the following expression:(6)ki↔j=Hki↔bs⊕kj↔bs.SNi also calculates broadcast pseudonym ID for SNj (BPIDj) according to expression (2). SNi has already received the values of IDj and bj through Mdiscovery. It also calculates the one-hop pseudonym ID (OHPIDi↔j) shared between SNi and SNj as expressed in the following expression:(7)OHPIDi↔j=Hai⊕aj.Finally, acknowledgement pseudonym ID for SNi (APIDi) will be calculated according to the expression below:(8)APIDi=HIDi.SNi will have a table TBLi which contains the shared values with the neighbors as listed in Table 1. Thus, we have replaced the ID withquintuple pseudonyms [4] to reference the SN during the communication. Figure 1 shows two sensors after they have exchanged the required pseudonyms.Table 1
Shared values among sensor neighbors. IfSNi has Ni neighbors, then TBLi will have N tuples, one tuple per a neighbor [4, 16].
Information inTi per each neighbor
Tuple forSNj
Shared random number
a
i
↔
j
Shared broadcast random number
b
j
Shared fake broadcast random number
c
j
Shared broadcast key
BPID
j
Shared fake broadcast key
FPID
j
Shared one-hop key
k
i
↔
j
Current one-hop pseudonym ID
OHPID
i
↔
j
Link direction
link
i
→
j
Residual energy level
Δ
jFigure 1
Two SN neighbors share the required pseudonyms.


### 5.1.2. Deleting Security Information

After storing all required pseudonyms, parameters, and keys inTBLi for SNi, it would be the time to delete all unnecessary information for the purpose of security [4, 16, 25]. In addition, it will release some memory storage space [16, 18]. Most importantly, SNi will delete IDi and HCi↔bs, which could be critical information for the adversary. In addition, SNi will delete discovery messages received earlier from the neighbors.


## 5.1.1. Issuing the Pseudonyms

A SN uses any issued pseudonym only once. That means we need to use a one disposable pseudonym per a transmission. There are five kinds of transmissions that could happen in the WSN [4, 16]: (i) multihop transmission between a SN and BS, (ii) transmission between two neighbor SNs, (iii) broadcast sent by a SN or the BS, (iv) acknowledgement, and (v) fake broadcast. The process starts by creating a pseudonym ID for each SNi, and we call it for short (PIDi) which is issued using the following expression:(1)PIDi=HIDi⊕ai.The SNi can calculate the broadcast pseudonym ID (BPIDi) according to the following expression:(2)BPIDi=HIDi⊕bi.The SNi can calculate the fake broadcast pseudonym ID (FBPIDi) according to the following expression:(3)FBPIDi=HIDi⊕ci.SNi should know its entire neighbor set Ni. A neighbor SNj is a sensor that could receive signal from the SNi and vice versa through one-hop transmission. SNi will send Mdiscovery, a broadcast discovery message, to exchange parameters with all one-hop neighbors. The format of the message is as follows:(4)Mdiscovery=kdis·TTL∥IDi∥ki↔bs∥kbi∥fkbi∥ai∥bi∥ci∥HCi↔bs.The value of TTL should beone for this transmission. SNi will receive also a similar broadcast message from SNj and from all other neighbors. Both SNi and SNj will calculate a new random value (ai↔j) according to the following expression:(5)ai↔j=HIDi⊕IDj.Both SNi and SNj will calculate also a new pairwise key ki↔j according to the following expression:(6)ki↔j=Hki↔bs⊕kj↔bs.SNi also calculates broadcast pseudonym ID for SNj (BPIDj) according to expression (2). SNi has already received the values of IDj and bj through Mdiscovery. It also calculates the one-hop pseudonym ID (OHPIDi↔j) shared between SNi and SNj as expressed in the following expression:(7)OHPIDi↔j=Hai⊕aj.Finally, acknowledgement pseudonym ID for SNi (APIDi) will be calculated according to the expression below:(8)APIDi=HIDi.SNi will have a table TBLi which contains the shared values with the neighbors as listed in Table 1. Thus, we have replaced the ID withquintuple pseudonyms [4] to reference the SN during the communication. Figure 1 shows two sensors after they have exchanged the required pseudonyms.Table 1
Shared values among sensor neighbors. IfSNi has Ni neighbors, then TBLi will have N tuples, one tuple per a neighbor [4, 16].
Information inTi per each neighbor
Tuple forSNj
Shared random number
a
i
↔
j
Shared broadcast random number
b
j
Shared fake broadcast random number
c
j
Shared broadcast key
BPID
j
Shared fake broadcast key
FPID
j
Shared one-hop key
k
i
↔
j
Current one-hop pseudonym ID
OHPID
i
↔
j
Link direction
link
i
→
j
Residual energy level
Δ
jFigure 1
Two SN neighbors share the required pseudonyms.


## 5.1.2. Deleting Security Information

After storing all required pseudonyms, parameters, and keys inTBLi for SNi, it would be the time to delete all unnecessary information for the purpose of security [4, 16, 25]. In addition, it will release some memory storage space [16, 18]. Most importantly, SNi will delete IDi and HCi↔bs, which could be critical information for the adversary. In addition, SNi will delete discovery messages received earlier from the neighbors.


## 5.2. Communication Phase

During the steady communication phase, when sensing and sending data by nodes to the BS takes place,seven operations continue until the network lifetime ends. These operations are [4] (i) sensing and sending a message to a neighbor, (ii) forwarding a message to a neighbor, (iii) broadcasting a message, (iv) acknowledgement, (v) sending a fake message, (vi) SN addition, and (vii) SN removal. A SN will have three roles, in terms of data transmission, during the communication phase [4, 16, 25]: (i) role as a sensor, (ii) as a forwarder or intermediary node, and (iii) as a broadcaster. In the following sections, we will use SNi as a source node and SNj as a neighbor to the source.


### 5.2.1. Transmission as a Sensor

WhenSNi senses data, it needs to send a message hop-by-hop to the BS. The SNi only recognizes itself by its newly calculated pseudonym (PIDi), and the BS will recognize source of the message through PIDi identity as well. Thus, the PIDi of the source needs to be included in the message until it reaches the BS. Consequently, the PID of a sensor will be updated after every transmission. When data is sensed and ready to be sent out, the SNi needs to select one neighbor from Ni to forward the message to it. The selection process goes through a probabilistic protocol which guarantees that SNi does not depend all the time on one neighbor when forwarding its data; first, for routing privacy and second for increasing the lifetime of the WSN. SNi will form the message in the following format:(9)Mi→j=OHPIDi↔j∥Eki→j·PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.Once SNi knows that the message (Mi→j) is delivered to the BS, it needs to dispose of the current pseudonym PIDi and issue a new one for the next transmission as indicated in the following expression:(10)PIDi=HPIDi⊕ai.In addition, both SNi and SNj will dispose of the current OHPIDi→j and issue a new one for the next communication between the two sensors according to following expression:(11)OHPIDi→j=HOHPIDi→j⊕ai→j.The message M will then be reformatted by the recipient SNj. Then, it will be forwarded to the next node, in the path, SNr, and so on, until it gets to the BS. If SNj was the BS, then the BS uses the shared one-hop key between the sensor and the BS to decrypt the encrypted data and gets the PIDi, which the BS can use to recognize the SNi. Thus, the BS will be able to recognize the originator of this message. Only at this point of time, BS can update the value of PIDi of SNi. It also gets the data (Di) which BS can read after decrypting the data by ki↔bs.


### 5.2.2. Transmission as a Forwarder

WhenSNi sends the message one-hop uplink to the neighbor SNj, SNj needs to forward the message to another intermediary node or in the best case to the BS if SNj is a neighbor of the BS. Upon receiving Mi→j, SNj will match OHPIDi→j in its table, Tj, under the column related to SNi. If there is no match, then the message definitely is not addressed for SNj and it will be dropped immediately. If it matches, then the message is addressed to SNj and it will be decrypt using ki→j. The message will be forwarded to SNr after M is reformatted as in(12)Mj→r=OHPIDj↔r∥Ekj→r·PIDi∥Eki↔bsDi∥HMACki↔bsPIDi∥Di.Right after the data isreceived by SNj andforwarded to the next one-hop SNr, the SNj updates both pseudonyms, OHPIDi↔j and OHPIDj↔r. SNj now is ready to exchange another message with SNi using the new pseudonym OHPIDi↔j. However, SNj is not yet ready to send data to SNr since SNr does not update the OHPIDj↔r until Di is forwarded to the next hop, say NSv. What would happen if SNj senses new data while it is busy forwarding a previous message? It has to wait until OHPIDj↔r is updated or it can use a different neighbor to forward the new message.


### 5.2.3. Acknowledgment

As expected in data networks, message could be lost or become corrupted. In either case, retransmission is required. Because SNs change PIDs after each transmission, synchronizing PIDs is crucial. Updating the pseudonyms depends on successful message transmission and reception. Technically, a sender and a receiver should alter the pseudonym value only after making sure that the data are sent correctly and received perfectly by the BS. The lack of direct connection between the sender and the receiver makes it a complicated process. The BS cannot send direct acknowledgement to the source if it is multiple hops away. We have to depend on multiple acknowledgements along the path between the source and the destination. Transmitting data through a route ofy hops needs y acknowledgements. SNi needs to calculate acknowledgement pseudonym ID (APIDi) according to the following expression:(13)APIDi=HAPIDi⊕bi.The message will be sent out now with the current value for APIDi. Thus, we will rewrite Mi→j as it appears in(14)Mi→j=Padding∥OHPIDi↔j∥Eki→j·APIDi∥PIDi∥Eki↔bs(Di)∥HMACki↔bs·PIDi∥Di.Padding is added to make sure all the one-hop packets have the same size to prevent ADV from identifying the source bytraffic analysisandsize correlation attacks. When SNj receives the packet, it will reformat the packet as in expression (15) and then will send it to SNr:(15)Mj→r=APIDi∥OHPIDj↔r∥Ej→r·APIDj∥PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.The transmission of Mj→r should be heard by all the neighbors including both SNi and SNr. If SNi hears the message and reads APIDi, the SNi knows that Mi→j was received correctly by SNj. Only at this time, SNi updates the value of OHPIDi↔j. PIDi will be updated, as well, since SNi is the source of the message. Here are two scenarios.Scenario 1.
The packet sent bySNi is lost or got corrupted. In this scenario, SNj considers nothing happened, so it will not forward any message onward. Meanwhile, SNi will wait for ζ time to expire. It will send the message again with updated APIDi. Once the message is acknowledged according to the procedure explained earlier and if the SN is the source, then PIDi, OHPIDi, and APIDi will be updated and be ready for a new packet to be sent out. If it is intermediary SN, only OHPIDi and APIDi are updated.Scenario 2.
The packet is received correctly bySNj, the new packet Mj→r is sent out including the acknowledgement APIDi, and SNj updated the value of OHPIDi↔j. However, SNi does not hear the forwarded message Mj→r within time ζ. At this moment, SNi does not know for sure if the packet was delivered or the acknowledgement is lost. It has to account for the worst-case scenario. A copy of the message will be retransmitted to SNj with the current OHPIDi and updated APIDi. SNj can recognize the message because of the value of old OHPIDi. After receiving theretransmitted packet, it now sends direct acknowledgement to SNi as in the following expression:(16)ACKi←j=APIDi∥Padding.BS is treated similar to normal SN, so it has to acknowledge every packet it receives. After the packet is delivered to the BS, and after the message is acknowledged, the PIDi (of the source) will be updated. Both the SNi and the BS will be ready to exchange a new message. As long as the new message does not reach the BS before the old PIDi is updated, the system will continue to be synchronized. This way, we have a possible window of one message. However, there is no guarantee to have all messages arrive in order. The only way to do it is if the system accounts for minimum interval time ωmin⁡, which is the minimum time span between two messages. However, in some cases, the packet cannot be delivered at all through a certain route. One obvious scenario is when an intermediate node is depleted out of energy before it forwards the message onward. The message needs to be rerouted through a different intermediate node which could cause a sever delay. We suggest implementing a sliding window mechanism as exhibited in Figure 2. For each sensor, we can have a window of W size. If we have k bits for the sequence number of the PID, then we can have a sliding window of 2k-1 slots. Once the BS finds out that the sequence of PIDs is not synchronized, it will send a message to resynchronize the sensor with the BS.Figure 2
Sliding window for received PIDs [19].


### 5.2.4. Transmission as a Broadcaster

Typically, the BS is required to broadcast messages for control and management purposes. Likewise, a sensor might need to broadcast a message to the BS for network setup, maintenance, and other management issues. A sensor, as well, could broadcast a message for emergency or urgency reasons depending on the application at hand. The framework requires keeping all the packets, transmitted throughout the network, indistinguishable by the adversary. Thus, all the messages need to have the samesize. Broadcast isone-to-many transmission; a SNi can broadcast a message to all the neighbors in the set Ni. Each SN is preloaded with a broadcast key (kbi) and assigned broadcast pseudonym ID (BPIDi). The broadcast message sent by SNi is formatted as in the following expression:(17)Mb=Padding∥BPIDi∥EkbiDb.The broadcast message from a source SNi will be received by all the neighbors ∈Ni. SNi and the recipients will update BPIDi according to the following expression: (18)BPIDi=H1BPIDi⊕bi.Upon receiving the broadcast message (Mb), SNj decrypts the message using the stored key (kbi) in the table TBLj. It then encrypts it again using kbj and broadcasts Mb to its one-hop neighbors set (Nj) as in the following expression:(19)Mb=BPIDi∥BPIDj∥EkbjDb.When the BS receives a broadcast message, it is ultimately the destination, so intuitively it does not need to broadcast the message again. Our proposed framework assumes that the BS behaves like a normal sensor. To maintain this precourse, we require the BS to broadcast the message again. Thus, we introduce the limited broadcast where the BS will broadcast only to one hop with TTL = 1. Likewise, to reduce the unnecessary traffic, we have required the intermediary nodes to rebroadcast only to the neighbors with smaller HC in case of uplink messages and to neighbors with bigger HC in case of downlink messages. What if the neighbors, with less HC, are all dead? We could end up with a section completely disconnected from the BS. The protocol needs to consider broadcast messages to all the neighbors in this case.


### 5.2.5. Limited Broadcast Messages

A sensor inside network maze can only recognize the neighbor sensors and the BS. When SN broadcasts a message uplink, then all sensor neighbors should hear it. When intermediary sensor gets broadcast message, it should rebroadcast the message if and only if the message is received from SN with bigger HC. This way the message is directed to the BS through multiple routes while saving unnecessary traffic. TheTTL=HCmax⁡ where HCmax⁡ preloaded at the startup phase. The value will keep reduced by one until it gets to the BS. In case of the downlink messages from the BS to all the sensors, the intermediary sensor would rebroadcast the message if and only if it is coming from a SN with smaller HC. In this case the message will hold TTL = 0 without change as an indication of BS as the source until it reaches all the sensors. The special case of broadcast is when TTL = 1 where the message will be broadcasted to one hop only.


### 5.2.6. Fake Broadcast Message

The sensors need to send fake messages to preventtime correlation attack and statistical analysis. The rate of the fake messages follows a certain protocol. Fake message is a one-hop broadcast message. However, to prevent correlation, the message needs to behave similar to real messages. Therefore, the message needs to be encrypted and has similar size as real messages. This will make the fake messages indistinguishable from the real messages. Since it has to carry a dummy data, we chose to make it carryresidual energy(Δ) of the source sensor. This information will be extracted by the recipient neighbors and saved in the related tuple in the table TBL. The fake broadcast message sent by SNi is explained in the following expression:(20)Mf=Padding∥FPIDi∥EkfiΔi.The fake broadcast message from SNi will be received by all the neighbors, for example, SNj, SNu, SNv∈Ni. SNi and the recipients will then update FPIDi according to expression (21)FPIDi=H1FPIDi⊕ci.There is no need to worry about the pseudonym synchronization since the main purpose of fake message is to show activity in idle sensors to obfuscate real messages.


## 5.2.1. Transmission as a Sensor

WhenSNi senses data, it needs to send a message hop-by-hop to the BS. The SNi only recognizes itself by its newly calculated pseudonym (PIDi), and the BS will recognize source of the message through PIDi identity as well. Thus, the PIDi of the source needs to be included in the message until it reaches the BS. Consequently, the PID of a sensor will be updated after every transmission. When data is sensed and ready to be sent out, the SNi needs to select one neighbor from Ni to forward the message to it. The selection process goes through a probabilistic protocol which guarantees that SNi does not depend all the time on one neighbor when forwarding its data; first, for routing privacy and second for increasing the lifetime of the WSN. SNi will form the message in the following format:(9)Mi→j=OHPIDi↔j∥Eki→j·PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.Once SNi knows that the message (Mi→j) is delivered to the BS, it needs to dispose of the current pseudonym PIDi and issue a new one for the next transmission as indicated in the following expression:(10)PIDi=HPIDi⊕ai.In addition, both SNi and SNj will dispose of the current OHPIDi→j and issue a new one for the next communication between the two sensors according to following expression:(11)OHPIDi→j=HOHPIDi→j⊕ai→j.The message M will then be reformatted by the recipient SNj. Then, it will be forwarded to the next node, in the path, SNr, and so on, until it gets to the BS. If SNj was the BS, then the BS uses the shared one-hop key between the sensor and the BS to decrypt the encrypted data and gets the PIDi, which the BS can use to recognize the SNi. Thus, the BS will be able to recognize the originator of this message. Only at this point of time, BS can update the value of PIDi of SNi. It also gets the data (Di) which BS can read after decrypting the data by ki↔bs.


## 5.2.2. Transmission as a Forwarder

WhenSNi sends the message one-hop uplink to the neighbor SNj, SNj needs to forward the message to another intermediary node or in the best case to the BS if SNj is a neighbor of the BS. Upon receiving Mi→j, SNj will match OHPIDi→j in its table, Tj, under the column related to SNi. If there is no match, then the message definitely is not addressed for SNj and it will be dropped immediately. If it matches, then the message is addressed to SNj and it will be decrypt using ki→j. The message will be forwarded to SNr after M is reformatted as in(12)Mj→r=OHPIDj↔r∥Ekj→r·PIDi∥Eki↔bsDi∥HMACki↔bsPIDi∥Di.Right after the data isreceived by SNj andforwarded to the next one-hop SNr, the SNj updates both pseudonyms, OHPIDi↔j and OHPIDj↔r. SNj now is ready to exchange another message with SNi using the new pseudonym OHPIDi↔j. However, SNj is not yet ready to send data to SNr since SNr does not update the OHPIDj↔r until Di is forwarded to the next hop, say NSv. What would happen if SNj senses new data while it is busy forwarding a previous message? It has to wait until OHPIDj↔r is updated or it can use a different neighbor to forward the new message.


## 5.2.3. Acknowledgment

As expected in data networks, message could be lost or become corrupted. In either case, retransmission is required. Because SNs change PIDs after each transmission, synchronizing PIDs is crucial. Updating the pseudonyms depends on successful message transmission and reception. Technically, a sender and a receiver should alter the pseudonym value only after making sure that the data are sent correctly and received perfectly by the BS. The lack of direct connection between the sender and the receiver makes it a complicated process. The BS cannot send direct acknowledgement to the source if it is multiple hops away. We have to depend on multiple acknowledgements along the path between the source and the destination. Transmitting data through a route ofy hops needs y acknowledgements. SNi needs to calculate acknowledgement pseudonym ID (APIDi) according to the following expression:(13)APIDi=HAPIDi⊕bi.The message will be sent out now with the current value for APIDi. Thus, we will rewrite Mi→j as it appears in(14)Mi→j=Padding∥OHPIDi↔j∥Eki→j·APIDi∥PIDi∥Eki↔bs(Di)∥HMACki↔bs·PIDi∥Di.Padding is added to make sure all the one-hop packets have the same size to prevent ADV from identifying the source bytraffic analysisandsize correlation attacks. When SNj receives the packet, it will reformat the packet as in expression (15) and then will send it to SNr:(15)Mj→r=APIDi∥OHPIDj↔r∥Ej→r·APIDj∥PIDi∥Eki↔bsDi∥HMACki↔bs·PIDi∥Di.The transmission of Mj→r should be heard by all the neighbors including both SNi and SNr. If SNi hears the message and reads APIDi, the SNi knows that Mi→j was received correctly by SNj. Only at this time, SNi updates the value of OHPIDi↔j. PIDi will be updated, as well, since SNi is the source of the message. Here are two scenarios.Scenario 1.
The packet sent bySNi is lost or got corrupted. In this scenario, SNj considers nothing happened, so it will not forward any message onward. Meanwhile, SNi will wait for ζ time to expire. It will send the message again with updated APIDi. Once the message is acknowledged according to the procedure explained earlier and if the SN is the source, then PIDi, OHPIDi, and APIDi will be updated and be ready for a new packet to be sent out. If it is intermediary SN, only OHPIDi and APIDi are updated.Scenario 2.
The packet is received correctly bySNj, the new packet Mj→r is sent out including the acknowledgement APIDi, and SNj updated the value of OHPIDi↔j. However, SNi does not hear the forwarded message Mj→r within time ζ. At this moment, SNi does not know for sure if the packet was delivered or the acknowledgement is lost. It has to account for the worst-case scenario. A copy of the message will be retransmitted to SNj with the current OHPIDi and updated APIDi. SNj can recognize the message because of the value of old OHPIDi. After receiving theretransmitted packet, it now sends direct acknowledgement to SNi as in the following expression:(16)ACKi←j=APIDi∥Padding.BS is treated similar to normal SN, so it has to acknowledge every packet it receives. After the packet is delivered to the BS, and after the message is acknowledged, the PIDi (of the source) will be updated. Both the SNi and the BS will be ready to exchange a new message. As long as the new message does not reach the BS before the old PIDi is updated, the system will continue to be synchronized. This way, we have a possible window of one message. However, there is no guarantee to have all messages arrive in order. The only way to do it is if the system accounts for minimum interval time ωmin⁡, which is the minimum time span between two messages. However, in some cases, the packet cannot be delivered at all through a certain route. One obvious scenario is when an intermediate node is depleted out of energy before it forwards the message onward. The message needs to be rerouted through a different intermediate node which could cause a sever delay. We suggest implementing a sliding window mechanism as exhibited in Figure 2. For each sensor, we can have a window of W size. If we have k bits for the sequence number of the PID, then we can have a sliding window of 2k-1 slots. Once the BS finds out that the sequence of PIDs is not synchronized, it will send a message to resynchronize the sensor with the BS.Figure 2
Sliding window for received PIDs [19].


## 5.2.4. Transmission as a Broadcaster

Typically, the BS is required to broadcast messages for control and management purposes. Likewise, a sensor might need to broadcast a message to the BS for network setup, maintenance, and other management issues. A sensor, as well, could broadcast a message for emergency or urgency reasons depending on the application at hand. The framework requires keeping all the packets, transmitted throughout the network, indistinguishable by the adversary. Thus, all the messages need to have the samesize. Broadcast isone-to-many transmission; a SNi can broadcast a message to all the neighbors in the set Ni. Each SN is preloaded with a broadcast key (kbi) and assigned broadcast pseudonym ID (BPIDi). The broadcast message sent by SNi is formatted as in the following expression:(17)Mb=Padding∥BPIDi∥EkbiDb.The broadcast message from a source SNi will be received by all the neighbors ∈Ni. SNi and the recipients will update BPIDi according to the following expression: (18)BPIDi=H1BPIDi⊕bi.Upon receiving the broadcast message (Mb), SNj decrypts the message using the stored key (kbi) in the table TBLj. It then encrypts it again using kbj and broadcasts Mb to its one-hop neighbors set (Nj) as in the following expression:(19)Mb=BPIDi∥BPIDj∥EkbjDb.When the BS receives a broadcast message, it is ultimately the destination, so intuitively it does not need to broadcast the message again. Our proposed framework assumes that the BS behaves like a normal sensor. To maintain this precourse, we require the BS to broadcast the message again. Thus, we introduce the limited broadcast where the BS will broadcast only to one hop with TTL = 1. Likewise, to reduce the unnecessary traffic, we have required the intermediary nodes to rebroadcast only to the neighbors with smaller HC in case of uplink messages and to neighbors with bigger HC in case of downlink messages. What if the neighbors, with less HC, are all dead? We could end up with a section completely disconnected from the BS. The protocol needs to consider broadcast messages to all the neighbors in this case.


## 5.2.5. Limited Broadcast Messages

A sensor inside network maze can only recognize the neighbor sensors and the BS. When SN broadcasts a message uplink, then all sensor neighbors should hear it. When intermediary sensor gets broadcast message, it should rebroadcast the message if and only if the message is received from SN with bigger HC. This way the message is directed to the BS through multiple routes while saving unnecessary traffic. TheTTL=HCmax⁡ where HCmax⁡ preloaded at the startup phase. The value will keep reduced by one until it gets to the BS. In case of the downlink messages from the BS to all the sensors, the intermediary sensor would rebroadcast the message if and only if it is coming from a SN with smaller HC. In this case the message will hold TTL = 0 without change as an indication of BS as the source until it reaches all the sensors. The special case of broadcast is when TTL = 1 where the message will be broadcasted to one hop only.


## 5.2.6. Fake Broadcast Message

The sensors need to send fake messages to preventtime correlation attack and statistical analysis. The rate of the fake messages follows a certain protocol. Fake message is a one-hop broadcast message. However, to prevent correlation, the message needs to behave similar to real messages. Therefore, the message needs to be encrypted and has similar size as real messages. This will make the fake messages indistinguishable from the real messages. Since it has to carry a dummy data, we chose to make it carryresidual energy(Δ) of the source sensor. This information will be extracted by the recipient neighbors and saved in the related tuple in the table TBL. The fake broadcast message sent by SNi is explained in the following expression:(20)Mf=Padding∥FPIDi∥EkfiΔi.The fake broadcast message from SNi will be received by all the neighbors, for example, SNj, SNu, SNv∈Ni. SNi and the recipients will then update FPIDi according to expression (21)FPIDi=H1FPIDi⊕ci.There is no need to worry about the pseudonym synchronization since the main purpose of fake message is to show activity in idle sensors to obfuscate real messages.


## 5.3. SN Removal

There are many reasons why we need to remove a sensor from the network. For instance, when the battery of the sensor is about to deplete, it should refrain from participating in transmission in preparation of removing it from the network. This would protect against lost data and keep the pseudonyms synchronized.In some cases, WSN uses intrusion detection system (IDS) [26], to protect against active attacks. Once SN is captured by the ADV, SN must be removed from the network and banned from participation in data transmission. Procedurally, if SNi opts to be removed, it sends two messages requesting the removal. The first message is to the BS as in expression(22)Mi→j=OHPIDi↔j∥Eki→jPIDi∥Eki↔bsDremove.The tuple of the SNi in the BS tables will be disabled permanently. The SNi will send a broadcast message to the neighbors according to(23)Mb=Padding∥BPIDi∥EkbiDremove.Once the neighbors get the message Dremove, they will delete the tuple related to SNi from the tables. Neighbors will refrain from exchanging messages with SNi. The same process could be established by the BS to remove a captured SN from the network.


## 5.4. SN Addition

To addSNi to the network, it will be preloaded with all setup parameters: IDu, au, bu, cu, H1, ku↔bs, and kbu, and fkbu. Right after deployment, SNi calculates the shared parameters with its neighbors. The BS should be trusted to run the process. Before sharing the calculated parameters with the SNi, the neighbors authenticate the new sensor. The BS will send special key kadd to all the nodes by a broadcast message. SNi will be preloaded with the same key as well. SNi and the neighbors will use this special key to authenticate with each other. Initially, the BS sends the following broadcast message to all of its one-hop neighbors as in the following expression(24)Mb=Padding∥BPIDbs∥Ekb-bsDadd,where Dadd is expressed in expression(25)Dadd=hc∥kadd.The initial value for hc is 0 where it represents the hop count. It will be incremented every time the message is forwarded.


## 6. Security Analysis

We need to analyze our solution for both passive and active ADV attacks. The ADV has global view of the WSN. Usually, ADV starts by monitoring transmission somewhere in the network and then attempts to capture the location of source SNs or the BS. Once ADV determines the identity and location of a source SN, it consequently launches active attacks against certain SNs and tries to disrupt the operation of the entire WSN. The main strength of passive ADV is the fact that neither SNs nor the BS will know about their existence since they act passively. However, active attacks can be detected if the WSN implements a good IDS.


### 6.1. Security against Passive Attacks

SNs use disposable pseudonyms to recognize each other instead of using the real IDs. There is absolutely no real ID stored in the SN and absolutely no one pseudonym is used more than once. In addition, data is encrypted all the way from the source to the destination using pairwise shared keys between sources and the BS.Eavesdropping and Content Analysis. ADV can intercept messages without being able to decrypt them because they are encrypted. The only information ADV can get of a captured message is the pseudonyms which are all temporary IDs and have no further use except to calculate new pseudonyms. However, the ADV cannot get, from the captured messages, important parameters ai↔j, bi, or ci which are required to calculated new pseudonyms. Thus, the ADV will not be able to create new pseudonyms.Hop-by-Hop Trace. ADV can track hop-by-hop messages from one node to another by overhearing the transmitted messages to capture either the source SN or the BS. The ADV will be faced with many real and fake transmissions, which are identical, during the lifetime of the WSN. Furthermore, each node uses different routes and the message content changes completely after each transmission.Size Correlation. This attack would not work for our framework since all the messages have commensurate size whether it is real or fake.Identity Correlation. ADV cannot relate overheard IDs to SNs. It is not possible since SNs use different pseudonyms every time a message is transmitted.Rate Monitoring. ADV tries to find different transmission rates in the network, such as having higher transmission rate nearby the BS or busy SNs. This is handled by issuing fake messages all over the network to maintain similar transmission rate over the lifetime of the WSN.


### 6.2. Security against Active Attacks

ADV couldphysically compromise SN which gives the ADV the advantage of monitoring messages sent and received through the captured SN. We assume ADV knows encryption protocols used by the system while the system hidesencryption keys and IDs. In such attacks, ADV tries to compromise SNs to get information related to security of the system. Consequently, it will monitor all packets going through the compromised SN to capture the identities and important parameters. Once ADV captures some privacy information, it reports it to external executers to do further damages (such as killing the Panda). Yet the IDS cannot detect that the SN is physically captured due to the passive behavior of ADV. In some other attacks, ADV captures SNs and actively forge messages, send replay messages, and do other forms of invasive attacks. Moreover, ADV could load powerful computers with captured credentials to launch more catastrophic attacks.If ADV physically compromises a SN, then it captures two sets of information:(i)
information related to the node itself: the current pseudonym PID, the parameters used to calculate the pseudonyms, the hash functions, the keys, and other information as listed in Notations;(ii)
information related to the neighbors as listed in Table1.In this case, the ADV will have all it needs to issue new pseudonyms and send messages out to the neighbors.Scenario 1.
If ADV physically compromisesSNi and if SNj and SNr∈Ni, so SNi knows some information about both SNj and SNr. However, it cannot calculate important information such as aj↔r which is required for one-hop communication between SNj and SNr [16]. The reason is SNi would need IDj and IDr, which are both deleted at the end of the startup phase. If SNi hears a message transmitted among the neighbors, then it cannot determine the source SN.Scenario 2.
If ADV physically compromises multiple SNs, let us call it setNcs, and collects number of messages, let us call it set Ncm. Then, the number of compromised PIDs is equal to Ncm since each message has one unique PID. If the source SNi∉Ncs, then ADV cannot know the source node [16].Scenario 3.
If the message sent by sourceSNi as in Scenario 2 passes through SNj∈Ncs or even through multiple compromised SNs, it will not be able to correlate the captured PID with SNi.Scenario 4.
If a message sent by sourceSNi and ∀SN∈Ni is also ∈Ncs (all neighbors arephysically compromised), then ADV will be able to know that SNi is the source.It is unrealistic situation to have many compromised SNs. However, this proves that one or very fewphysically compromised SNs do not for sure leak the ID and location of the SN. None of the literature we have seen discussed this worse-case situation where you have physically compromised SNs. We have proved that even if we have some physically compromised nodes, our system still can limit the leak of the IDs and locations.


### 6.3. BS Security

ADV can learn about a SN receiving a message in two ways: (i) when SN retransmits the message, which is traced by ADV and (ii) the ADV being able to correlate the ID with the recipient SN. ADV cannot locate the BS by one compromised SN because every message uses a different pseudonym. It will need to compromise multiple SNs along the path to the BS, providing that compromised SNs can collude together. The goal of this model is to delay the capturing of the BS in the presence of multiple captured and colluding SNs.Let us presumeSNr∈Ncs. It issues a message with Db such that APIDr∥OHPIDr↔u∥Er→u(APIDr∥PIDr∥Ekr↔bs(Db)) [4]. If ADV compromises multiple nodes along the path to the BS where it can decrypt the data at each SN to always read this signature (PIDr∥Ekr↔bs(Db)). Reading the similar signature, while ADV knows that every message should be directed uplink to the BS tells the ADV that it is in the right path to get the BS. Compromised SNs can even collude to force the message to route through certain area in effort to focus the search for the BS. This way, it will be able to locate the BS sooner which is a function of (i) the size of the network, (ii) the traffic density in the network, and (iii) the number of compromised SNs. To solve this issue, the message signature (PIDr∥Ekr↔bs(Db)) needs to be scrambled at every hop. So, every message will be forwarded to the next hop as follows:(26)Mu→x=APIDu∥OHPIDu↔x∥Eu→x·APIDu∥PIDr∥PIDu∥Eku↔bsEkr↔bsDi.We have added multiple levels of encryption, which will be done at every hop using the shared key between the hop and the BS. In addition, PID of the hop will be added in sequence, so the BS can do the decryption in sequence upon message arrival. This solution increases the size of the message proportionally to the number of hops the message goes through. It will also add multiple levels of decryption at the BS. We suggest having the onion encryption done for a distance of few hops, Oh [4]. So, if Oh=2, then we have only two extra encryptions. In addition, we need to account for two PID’s added to the message. This size of Oh can be adjusted by the closed-loop control system according to the security needs and the WSN environment.


### 6.4. SLP and BSLP

SLP and BSLP are achieved at first by having successful source, link, and BS anonymity, which was thoroughly argued earlier. ADV cannot infer any information from the intercepted messages. Passive attacks will not endanger the location privacy. Having IDS will handle active attacks. However, having active attacks by physically compromised SNs could hinder the location privacy if many SNs are captured in one area.


### 6.5. Timing Privacy

By using fake messages at variable interval times, it becomes super hard for the ADV to correlate messages being transmitted over the network as exhibited in Figure3.Figure 3
(a) Sensors sense events and send real messages while the rest send fake messages, with fake MSG’s:Pr=1/N=1/48=2% and without fake MSG’s: Pr=1/n=1/11=9%. (b) Sensors sending new real or forward messages will not send fake messages. The more the network gets busy the less fake messages transmitted [19, 20].
(a)
(b)


### 6.6. Routing Privacy

Although shortest path routing is used in this framework, choosing the next hop is done according to certainprobabilistic algorithm, which accounts for the residual energy levels and usage frequency to increase the route privacy, as exhibited in Algorithm 1 and Figure 4. ADV cannot relate routes to nodes [20]. Even if two messages follow the exact same route, ADV will see them as if they are two different routes since each node along the route has different PIDs.Algorithm 1:Selecting the forward SN according to the residual energy level.
Procedure: SELECT_FORWARD_NODE_PROC;
Input:Ni
Output: Messages out
Δ
=
0;
fori in Ni        // total number of neighbors
{
Δ
=
Δ
+
SN
[
i
,
Δ
];}
Average_Δ = Δ/Ni;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == uplink) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == equal-link) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == down-link) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;Figure 4
How to choose the forwarding node according to the energy levels of the neighboring sensors [19, 20].


### 6.7. Data Privacy

Messages are encrypted before transmission and reencrypted at every hop along the route to the BS. Data will be authenticated by a message digest created by a secure hash function. The physically compromised nodes are able to inject data in the network but good IDS can detect the falsified data. The system adopts a secure procedure to remove compromised SNs from the WSN and adopts another procedure to add sensors as needed.


### 6.8. Energy and Location Safety Period

In this work, we will assume a simple energy consumption model [20, 27, 28]. The radio consumes ℇ nJ/bit for both transmission and reception by the SN’s circuitry. In addition, it consumes ε nJ/bit/m2 for the transmitter amplifier to achieve an acceptable signal to noise ratio. Therefore, to transmit k bits for r distance, the total transmission energy dissipation will be(27)Etrans⁡=k∗ℇ+k∗r2∗ε.Moreover, the receiver would consume for reception ofk-bit message(28)Ereceiv=k∗ℇ.The energy spent for transmission or reception is almost constant per a message since we have fixed-size messages to prevent size correlation attacks. If we have p percent of the nodes issue fake data at a specific period, then p percent of the energy and the bandwidth is wasted for the sake of WSN rate privacy. The consumption of transmitting fake messages is a double-fold since the transmitter will consume Etrans⁡ for every message and all the neighbors n will consume (n∗Etrans⁡). When the transmission range increases, n increases. The total energy consumed in the network to send real messages in one interval, where (q) is the average percentage of SNs sending or forwarding real messages and (n) is the average SN neighbors [28], is as follows: (29)ER=q∗Nk∗ℇ+k∗r2∗ε+q∗N∗nk∗ℇ.The exact value ofq cannot be known since it is an event driven value, which depends on the situation of the WSN at that time. The total energy consumed in the network to send fake messages in one interval where (p) is the specified percentage value of fake messages at one interval is as follows: (30)EF=p∗N∗k∗ℇ+k∗r2∗ε+p∗N∗n∗k∗ℇ.Energy transmission efficiency ETE [20] can be calculated as(31)ETE=ERER+EF.The energy safety period is the time when the first sensor is depleted. However, transmission of data is distributed among all sensors to make sure the safety period lasts longer. The level of the energy in every sensor is measured and considered as a decision factor (among others) for selecting the next-hop for the message. This will definitely help to distribute the network accumulative energy consumption over the whole WSN. The location safety period is the period between capturing the first packet and finding out the location of the source or the BS. It is measured as the ratio between the period of discovering the location and the interval period [25]. We have implemented a WSN of 300 SNs uniformly distributed over 200 × 200 area. The average distance between SNs is 15. For the simulation, a SN sends only 10% fake message of the total messages. That means that, among ten real messages, it will send only one fake message since we presumed a busy network. This could be scaled up or down. Increasing the fake message will increase the power dissipation.Figure5 shows that EEAC provides improved source safety period compared to EAC [4]. Figure 6 shows that EEAC also provides a stronger BS safety period compared to EAC [4]. However, the source safety period is much more than the sink safety period in both schemes. It is always harder to achieve BSLP due to the volume of transmissions nearby the BS. The efficiency of energy dissipation is due to adopting Algorithm 1 for selecting the forward SN where it takes in consideration the residual energy levels of the SNs, which was not considered in EAC. Figure 7 shows the delay in EEAC is very comparable to the EAC due the extra processing and security implementation. Furthermore, Figure 8 shows that the average total delivery time source-to-BS is also very comparable to EAC.Figure 5
Source safety period.Figure 6
BS safety period.Figure 7
Transmission delay.Figure 8
Message delivery time.


## 6.1. Security against Passive Attacks

SNs use disposable pseudonyms to recognize each other instead of using the real IDs. There is absolutely no real ID stored in the SN and absolutely no one pseudonym is used more than once. In addition, data is encrypted all the way from the source to the destination using pairwise shared keys between sources and the BS.Eavesdropping and Content Analysis. ADV can intercept messages without being able to decrypt them because they are encrypted. The only information ADV can get of a captured message is the pseudonyms which are all temporary IDs and have no further use except to calculate new pseudonyms. However, the ADV cannot get, from the captured messages, important parameters ai↔j, bi, or ci which are required to calculated new pseudonyms. Thus, the ADV will not be able to create new pseudonyms.Hop-by-Hop Trace. ADV can track hop-by-hop messages from one node to another by overhearing the transmitted messages to capture either the source SN or the BS. The ADV will be faced with many real and fake transmissions, which are identical, during the lifetime of the WSN. Furthermore, each node uses different routes and the message content changes completely after each transmission.Size Correlation. This attack would not work for our framework since all the messages have commensurate size whether it is real or fake.Identity Correlation. ADV cannot relate overheard IDs to SNs. It is not possible since SNs use different pseudonyms every time a message is transmitted.Rate Monitoring. ADV tries to find different transmission rates in the network, such as having higher transmission rate nearby the BS or busy SNs. This is handled by issuing fake messages all over the network to maintain similar transmission rate over the lifetime of the WSN.


## 6.2. Security against Active Attacks

ADV couldphysically compromise SN which gives the ADV the advantage of monitoring messages sent and received through the captured SN. We assume ADV knows encryption protocols used by the system while the system hidesencryption keys and IDs. In such attacks, ADV tries to compromise SNs to get information related to security of the system. Consequently, it will monitor all packets going through the compromised SN to capture the identities and important parameters. Once ADV captures some privacy information, it reports it to external executers to do further damages (such as killing the Panda). Yet the IDS cannot detect that the SN is physically captured due to the passive behavior of ADV. In some other attacks, ADV captures SNs and actively forge messages, send replay messages, and do other forms of invasive attacks. Moreover, ADV could load powerful computers with captured credentials to launch more catastrophic attacks.If ADV physically compromises a SN, then it captures two sets of information:(i)
information related to the node itself: the current pseudonym PID, the parameters used to calculate the pseudonyms, the hash functions, the keys, and other information as listed in Notations;(ii)
information related to the neighbors as listed in Table1.In this case, the ADV will have all it needs to issue new pseudonyms and send messages out to the neighbors.Scenario 1.
If ADV physically compromisesSNi and if SNj and SNr∈Ni, so SNi knows some information about both SNj and SNr. However, it cannot calculate important information such as aj↔r which is required for one-hop communication between SNj and SNr [16]. The reason is SNi would need IDj and IDr, which are both deleted at the end of the startup phase. If SNi hears a message transmitted among the neighbors, then it cannot determine the source SN.Scenario 2.
If ADV physically compromises multiple SNs, let us call it setNcs, and collects number of messages, let us call it set Ncm. Then, the number of compromised PIDs is equal to Ncm since each message has one unique PID. If the source SNi∉Ncs, then ADV cannot know the source node [16].Scenario 3.
If the message sent by sourceSNi as in Scenario 2 passes through SNj∈Ncs or even through multiple compromised SNs, it will not be able to correlate the captured PID with SNi.Scenario 4.
If a message sent by sourceSNi and ∀SN∈Ni is also ∈Ncs (all neighbors arephysically compromised), then ADV will be able to know that SNi is the source.It is unrealistic situation to have many compromised SNs. However, this proves that one or very fewphysically compromised SNs do not for sure leak the ID and location of the SN. None of the literature we have seen discussed this worse-case situation where you have physically compromised SNs. We have proved that even if we have some physically compromised nodes, our system still can limit the leak of the IDs and locations.


## 6.3. BS Security

ADV can learn about a SN receiving a message in two ways: (i) when SN retransmits the message, which is traced by ADV and (ii) the ADV being able to correlate the ID with the recipient SN. ADV cannot locate the BS by one compromised SN because every message uses a different pseudonym. It will need to compromise multiple SNs along the path to the BS, providing that compromised SNs can collude together. The goal of this model is to delay the capturing of the BS in the presence of multiple captured and colluding SNs.Let us presumeSNr∈Ncs. It issues a message with Db such that APIDr∥OHPIDr↔u∥Er→u(APIDr∥PIDr∥Ekr↔bs(Db)) [4]. If ADV compromises multiple nodes along the path to the BS where it can decrypt the data at each SN to always read this signature (PIDr∥Ekr↔bs(Db)). Reading the similar signature, while ADV knows that every message should be directed uplink to the BS tells the ADV that it is in the right path to get the BS. Compromised SNs can even collude to force the message to route through certain area in effort to focus the search for the BS. This way, it will be able to locate the BS sooner which is a function of (i) the size of the network, (ii) the traffic density in the network, and (iii) the number of compromised SNs. To solve this issue, the message signature (PIDr∥Ekr↔bs(Db)) needs to be scrambled at every hop. So, every message will be forwarded to the next hop as follows:(26)Mu→x=APIDu∥OHPIDu↔x∥Eu→x·APIDu∥PIDr∥PIDu∥Eku↔bsEkr↔bsDi.We have added multiple levels of encryption, which will be done at every hop using the shared key between the hop and the BS. In addition, PID of the hop will be added in sequence, so the BS can do the decryption in sequence upon message arrival. This solution increases the size of the message proportionally to the number of hops the message goes through. It will also add multiple levels of decryption at the BS. We suggest having the onion encryption done for a distance of few hops, Oh [4]. So, if Oh=2, then we have only two extra encryptions. In addition, we need to account for two PID’s added to the message. This size of Oh can be adjusted by the closed-loop control system according to the security needs and the WSN environment.


## 6.4. SLP and BSLP

SLP and BSLP are achieved at first by having successful source, link, and BS anonymity, which was thoroughly argued earlier. ADV cannot infer any information from the intercepted messages. Passive attacks will not endanger the location privacy. Having IDS will handle active attacks. However, having active attacks by physically compromised SNs could hinder the location privacy if many SNs are captured in one area.


## 6.5. Timing Privacy

By using fake messages at variable interval times, it becomes super hard for the ADV to correlate messages being transmitted over the network as exhibited in Figure3.Figure 3
(a) Sensors sense events and send real messages while the rest send fake messages, with fake MSG’s:Pr=1/N=1/48=2% and without fake MSG’s: Pr=1/n=1/11=9%. (b) Sensors sending new real or forward messages will not send fake messages. The more the network gets busy the less fake messages transmitted [19, 20].
(a)
(b)


## 6.6. Routing Privacy

Although shortest path routing is used in this framework, choosing the next hop is done according to certainprobabilistic algorithm, which accounts for the residual energy levels and usage frequency to increase the route privacy, as exhibited in Algorithm 1 and Figure 4. ADV cannot relate routes to nodes [20]. Even if two messages follow the exact same route, ADV will see them as if they are two different routes since each node along the route has different PIDs.Algorithm 1:Selecting the forward SN according to the residual energy level.
Procedure: SELECT_FORWARD_NODE_PROC;
Input:Ni
Output: Messages out
Δ
=
0;
fori in Ni        // total number of neighbors
{
Δ
=
Δ
+
SN
[
i
,
Δ
];}
Average_Δ = Δ/Ni;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == uplink) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == equal-link) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;
fori in Ni
{
x = Average_Δ;
if  (SN[i, link] == down-link) && (SN[i, Δ] >= x)
J = SN[i, OHPID]
X = SN[i, Δ];
}
Ifj != null
Return;Figure 4
How to choose the forwarding node according to the energy levels of the neighboring sensors [19, 20].


## 6.7. Data Privacy

Messages are encrypted before transmission and reencrypted at every hop along the route to the BS. Data will be authenticated by a message digest created by a secure hash function. The physically compromised nodes are able to inject data in the network but good IDS can detect the falsified data. The system adopts a secure procedure to remove compromised SNs from the WSN and adopts another procedure to add sensors as needed.


## 6.8. Energy and Location Safety Period

In this work, we will assume a simple energy consumption model [20, 27, 28]. The radio consumes ℇ nJ/bit for both transmission and reception by the SN’s circuitry. In addition, it consumes ε nJ/bit/m2 for the transmitter amplifier to achieve an acceptable signal to noise ratio. Therefore, to transmit k bits for r distance, the total transmission energy dissipation will be(27)Etrans⁡=k∗ℇ+k∗r2∗ε.Moreover, the receiver would consume for reception ofk-bit message(28)Ereceiv=k∗ℇ.The energy spent for transmission or reception is almost constant per a message since we have fixed-size messages to prevent size correlation attacks. If we have p percent of the nodes issue fake data at a specific period, then p percent of the energy and the bandwidth is wasted for the sake of WSN rate privacy. The consumption of transmitting fake messages is a double-fold since the transmitter will consume Etrans⁡ for every message and all the neighbors n will consume (n∗Etrans⁡). When the transmission range increases, n increases. The total energy consumed in the network to send real messages in one interval, where (q) is the average percentage of SNs sending or forwarding real messages and (n) is the average SN neighbors [28], is as follows: (29)ER=q∗Nk∗ℇ+k∗r2∗ε+q∗N∗nk∗ℇ.The exact value ofq cannot be known since it is an event driven value, which depends on the situation of the WSN at that time. The total energy consumed in the network to send fake messages in one interval where (p) is the specified percentage value of fake messages at one interval is as follows: (30)EF=p∗N∗k∗ℇ+k∗r2∗ε+p∗N∗n∗k∗ℇ.Energy transmission efficiency ETE [20] can be calculated as(31)ETE=ERER+EF.The energy safety period is the time when the first sensor is depleted. However, transmission of data is distributed among all sensors to make sure the safety period lasts longer. The level of the energy in every sensor is measured and considered as a decision factor (among others) for selecting the next-hop for the message. This will definitely help to distribute the network accumulative energy consumption over the whole WSN. The location safety period is the period between capturing the first packet and finding out the location of the source or the BS. It is measured as the ratio between the period of discovering the location and the interval period [25]. We have implemented a WSN of 300 SNs uniformly distributed over 200 × 200 area. The average distance between SNs is 15. For the simulation, a SN sends only 10% fake message of the total messages. That means that, among ten real messages, it will send only one fake message since we presumed a busy network. This could be scaled up or down. Increasing the fake message will increase the power dissipation.Figure5 shows that EEAC provides improved source safety period compared to EAC [4]. Figure 6 shows that EEAC also provides a stronger BS safety period compared to EAC [4]. However, the source safety period is much more than the sink safety period in both schemes. It is always harder to achieve BSLP due to the volume of transmissions nearby the BS. The efficiency of energy dissipation is due to adopting Algorithm 1 for selecting the forward SN where it takes in consideration the residual energy levels of the SNs, which was not considered in EAC. Figure 7 shows the delay in EEAC is very comparable to the EAC due the extra processing and security implementation. Furthermore, Figure 8 shows that the average total delivery time source-to-BS is also very comparable to EAC.Figure 5
Source safety period.Figure 6
BS safety period.Figure 7
Transmission delay.Figure 8
Message delivery time.


## 7. Performance Evaluation

In this section, we evaluate the performance of our system, by evaluating the storage, processing, computational, and communication costs.


### 7.1. Storage Evaluation

There are two sets of information stored in aSNi: (i) information related to the sensor itself, such as random numbers: (ai,bi,ci), pseudonyms: (PIDi,BPIDi,FPIDi,APIDi), keys: (ki↔bs,kbi,fkbi) and (ii) information related to each neighbors which includes random numbers: (ai↔j,bj,cj), pseudonyms: (OHPIDi↔j,BPIDj,FPIDj), and keys: (ki↔j), Misc: (linki↔j,Δj).If we presume that the keys, the random numbers, the pseudonyms, and the hash functions are alln bits long in average and the required bits for miscellaneous data altogether aretwo bytes and the average number of neighbors Nave, then the total storage memory required is (32)Storage=10n+7n+16∗Nave.Chen et al. [16] indicated the storage for SAS, CAS, APR, DCARPS, and EAC. We also calculated the storage for PhID, ACS, HIR, and RHIR. All are listed in Table 2. The size of storage proportionally increases when the size of n increases. The most common hashing functions are MD4 [29] which uses 128-bit digest, SHA-1 [29] which uses 160-bit digest, andWhirlpool [29] which uses 512-bit digest. The size of the storage would increase when the number of neighbors increases. Each SN has limited flash memory size, which could confine the maximum number of neighbors that a sensor can fit. As an example, TelosB mote [11, 16] has 1 MB external flash memory. Thus, if one neighbor node requires 1.2 k bits of storage memory, then TelosB could have more than 800 neighbors, which is very much more than what is needed in practical networks. Although our model shows a bit of increase in the storage required to store the pseudonyms but it is the only one among discussed protocols in this work that provides a steady and functional anonymity and location privacy under sever global and active attack. In addition, the current technology provides enough storage, which makes it no issue at all.Table 2
Performance comparison.N is the total number of sensors; Nave is the average number of neighbors;  k is number of stored hash values where the SN stores k hash values per one neighbor which are calculated in advance at startup phase [4, 16, 19, 25].
Scheme
Storage cost (bits)
Computation cost
1
SAS
2
n
N
+
4
n
N
ave
+
16
No hashing operations
2
CAS
6
n
+
7
n
N
ave
+
16
Two hashing operations and two encryptions
3
HIR
2
n
+
2
n
N
ave
One hashing function
4
RHIR
2
n
+
2
n
N
ave
+
n
k
N
ave
No hashing functions
5
APR
9
n
+
7
n
N
ave
+
2
N
-
2
N
ave
-
2
Six hashing functions
6
DCARPS and Global DCARPS
3
n
No hashing functions
7
ACS
5
n
N
ave
Two hashing functions
8
PhID
(
3
n
+
2
)
∗
N
ave
Four hashing functions
9
EAC
6
n
+
6
n
N
ave
+
2
Four hashing operations
10
E2AC
10
n
+
(
7
n
+
16
)
∗
N
ave
Four hashing operations andOh encryptions


### 7.2. Processing and Computational Evaluation

Hash functions are used to calculate the pseudonyms and symmetric cryptography is used to encrypt the messages. Because we need to calculate three pseudonyms and one acknowledgement after each transmission, thus using encryption to create pseudonyms was avoided since it requires more processing power compared to hash functions. When a SN senses data, it needs to have OWH calculations for PID, OHPID, and APID at the sender and OHPID at the receiver. If the system opts for data authentication, then another hash function is needed. The source node needs only one encryption for the data ifOh=0; however, it needs Oh more encryptions if onion fashion is used [4]. Each intermediary node needs one decryption operation and then another encryption for the new data. Chen et al. [16] indicates that SAS does not use hashing or encryption to create pseudonyms because it uses already created pseudonyms from a space. The other scheme by Chen et al. [16], CAS, uses two hashing operations and two encryption operations. APR uses at least six hashing functions. DCARPS uses constant IDs, so there are no hashing functions or encryptions for creating IDs. EAC has four hashing operations. None of the other schemes can achieve privacy against global threats and active adversary attacks. The power consumption due to the additional encryption operations is marginal compared to the power consumption caused by data transmission.


### 7.3. Communication Cost Evaluation

The most expensive operation for power consumption is transmission of bits from one node to another. We use two stages for air communication in our framework: (i) the startup phase and (ii) the communication phase. The data transmission during startup phase is minimal since the BS beacon and the neighbors’ information exchange happens once before the steady communication phase. During communication phase, data will be forwarded hop-by-hop to the BS. Every packet is equally sized to prevent time and size correlation. We have introduced a probabilistic fake packet transmission scheme which none of the other protocols adopted. When a SN does not have real message, it will send fake message according to the protocol discussed earlier.The cost per message at one interval time is(33)AverageMessageCost=R+N-RPr+AR,where R is the total number of SNs with real messages at one interval time, Pr the probability of sending fake message by SNs, and A the average number of acknowledgements in one interval. None of the other schemes addressed the issue of rate analysis attacks, which is one of the easiest attacks any adversary can use. Using fake messages is an expensive solution. However, we have designed our model to be adaptive to the network traffic situation by using a closed-loop system. The BS can always increase or decrease the amount of fake messages used according to the reports it is getting about the system security.


## 7.1. Storage Evaluation

There are two sets of information stored in aSNi: (i) information related to the sensor itself, such as random numbers: (ai,bi,ci), pseudonyms: (PIDi,BPIDi,FPIDi,APIDi), keys: (ki↔bs,kbi,fkbi) and (ii) information related to each neighbors which includes random numbers: (ai↔j,bj,cj), pseudonyms: (OHPIDi↔j,BPIDj,FPIDj), and keys: (ki↔j), Misc: (linki↔j,Δj).If we presume that the keys, the random numbers, the pseudonyms, and the hash functions are alln bits long in average and the required bits for miscellaneous data altogether aretwo bytes and the average number of neighbors Nave, then the total storage memory required is (32)Storage=10n+7n+16∗Nave.Chen et al. [16] indicated the storage for SAS, CAS, APR, DCARPS, and EAC. We also calculated the storage for PhID, ACS, HIR, and RHIR. All are listed in Table 2. The size of storage proportionally increases when the size of n increases. The most common hashing functions are MD4 [29] which uses 128-bit digest, SHA-1 [29] which uses 160-bit digest, andWhirlpool [29] which uses 512-bit digest. The size of the storage would increase when the number of neighbors increases. Each SN has limited flash memory size, which could confine the maximum number of neighbors that a sensor can fit. As an example, TelosB mote [11, 16] has 1 MB external flash memory. Thus, if one neighbor node requires 1.2 k bits of storage memory, then TelosB could have more than 800 neighbors, which is very much more than what is needed in practical networks. Although our model shows a bit of increase in the storage required to store the pseudonyms but it is the only one among discussed protocols in this work that provides a steady and functional anonymity and location privacy under sever global and active attack. In addition, the current technology provides enough storage, which makes it no issue at all.Table 2
Performance comparison.N is the total number of sensors; Nave is the average number of neighbors;  k is number of stored hash values where the SN stores k hash values per one neighbor which are calculated in advance at startup phase [4, 16, 19, 25].
Scheme
Storage cost (bits)
Computation cost
1
SAS
2
n
N
+
4
n
N
ave
+
16
No hashing operations
2
CAS
6
n
+
7
n
N
ave
+
16
Two hashing operations and two encryptions
3
HIR
2
n
+
2
n
N
ave
One hashing function
4
RHIR
2
n
+
2
n
N
ave
+
n
k
N
ave
No hashing functions
5
APR
9
n
+
7
n
N
ave
+
2
N
-
2
N
ave
-
2
Six hashing functions
6
DCARPS and Global DCARPS
3
n
No hashing functions
7
ACS
5
n
N
ave
Two hashing functions
8
PhID
(
3
n
+
2
)
∗
N
ave
Four hashing functions
9
EAC
6
n
+
6
n
N
ave
+
2
Four hashing operations
10
E2AC
10
n
+
(
7
n
+
16
)
∗
N
ave
Four hashing operations andOh encryptions


## 7.2. Processing and Computational Evaluation

Hash functions are used to calculate the pseudonyms and symmetric cryptography is used to encrypt the messages. Because we need to calculate three pseudonyms and one acknowledgement after each transmission, thus using encryption to create pseudonyms was avoided since it requires more processing power compared to hash functions. When a SN senses data, it needs to have OWH calculations for PID, OHPID, and APID at the sender and OHPID at the receiver. If the system opts for data authentication, then another hash function is needed. The source node needs only one encryption for the data ifOh=0; however, it needs Oh more encryptions if onion fashion is used [4]. Each intermediary node needs one decryption operation and then another encryption for the new data. Chen et al. [16] indicates that SAS does not use hashing or encryption to create pseudonyms because it uses already created pseudonyms from a space. The other scheme by Chen et al. [16], CAS, uses two hashing operations and two encryption operations. APR uses at least six hashing functions. DCARPS uses constant IDs, so there are no hashing functions or encryptions for creating IDs. EAC has four hashing operations. None of the other schemes can achieve privacy against global threats and active adversary attacks. The power consumption due to the additional encryption operations is marginal compared to the power consumption caused by data transmission.


## 7.3. Communication Cost Evaluation

The most expensive operation for power consumption is transmission of bits from one node to another. We use two stages for air communication in our framework: (i) the startup phase and (ii) the communication phase. The data transmission during startup phase is minimal since the BS beacon and the neighbors’ information exchange happens once before the steady communication phase. During communication phase, data will be forwarded hop-by-hop to the BS. Every packet is equally sized to prevent time and size correlation. We have introduced a probabilistic fake packet transmission scheme which none of the other protocols adopted. When a SN does not have real message, it will send fake message according to the protocol discussed earlier.The cost per message at one interval time is(33)AverageMessageCost=R+N-RPr+AR,where R is the total number of SNs with real messages at one interval time, Pr the probability of sending fake message by SNs, and A the average number of acknowledgements in one interval. None of the other schemes addressed the issue of rate analysis attacks, which is one of the easiest attacks any adversary can use. Using fake messages is an expensive solution. However, we have designed our model to be adaptive to the network traffic situation by using a closed-loop system. The BS can always increase or decrease the amount of fake messages used according to the reports it is getting about the system security.


## 8. Conclusions and Future Work

The scheme presented in this work provides source, link, and BS anonymity, SLP and BSLP. Most of the previous work assumed local adversary view and passive attack model. This work addressed local and global adversary network view. It handles both passive and active attack models. Anonymity cannot provide temporal privacy. To provide temporal privacy, the global adversary needs to see a maze of transmissions happening all over the network. Fake messages were introduced. However, using fake messages needs to be adjusted to manage the energy consumption. The presented model can handle both homogenous and heterogeneous sensor nodes in terms of initial energy levels. It uses the energy level as the main indicator in deciding how to route packets forward. We have demonstrated that our framework can withstand most of the known passive and active attacks. We have discussed many scenarios and provided solutions. The storage cost was mathematically analyzed for the framework. We also have discussed the complexity of computational operations performed in the system, which includes encryption and hash functions. To provide security against multi colluding active attackers, we have introduced onion encryptions. The future work would include enhancement on the probabilistic scheme for fake messages usage. We also will implement our model for clustered networks.



---

*Source: 697098-2015-04-15.xml*