Effective Key Management in DynamicWireless Sensor NetworksAbstract—Recently, wireless sensor networks (WSNs) havebeen deployed for a wide variety of applications, includingmilitary sensing and tracking, patient status monitoring, trafficflow monitoring, where sensory devices often move betweendifferent locations. Securing data and communications requiressuitable encryption key protocols. In this paper, we propose acertificateless-effective key management (CL-EKM) protocol forsecure communication in dynamic WSNs characterized by nodemobility. The CL-EKM supports efficient key updates when anode leaves or joins a cluster and ensures forward and backwardkey secrecy. The protocol also supports efficient key revocationfor compromised nodes and minimizes the impact of a nodecompromise on the security of other communication links.A security analysis of our scheme shows that our protocol is effectivein defending against various attacks.We implement CL-EKMin Contiki OS and simulate it using Cooja simulator to assess itstime, energy, communication, and memory performance.Index Terms—Wireless sensor networks, certificateless publickey cryptography, key management scheme.I. INTRODUCTIONDYNAMIC wireless sensor networks (WSNs), whichenable mobility of sensor nodes, facilitate wider networkcoverage and more accurate service than static WSNs. Therefore,dynamic WSNs are being rapidly adopted in monitoringapplications, such as target tracking in battlefield surveillance,healthcare systems, traffic flow and vehicle status monitoring,dairy cattle health monitoring [9]. However, sensor devicesare vulnerable to malicious attacks such as impersonation,interception, capture or physical destruction, due to theirunattended operative environments and lapses of connectivityin wireless communication [20]. Thus, security is one ofthe most important issues in many critical dynamic WSNapplications. DynamicWSNs thus need to address key securityrequirements, such as node authentication, data confidentialityand integrity, whenever and wherever the nodes move.To address security, encryption key management protocolsfor dynamic WSNs have been proposed in the past basedManuscript received August 6, 2014; revised October 17, 2014; acceptedNovember 18, 2014. Date of publication December 4, 2014; date of currentversion January 13, 2015. This work was supported in part by the BrainKorea 21 Plus Project. The associate editor coordinating the review of thismanuscript and approving it for publication was Prof. Kui Q. Ren.S.-H. Seo is with the Center for Information Security Technologies, KoreaUniversity, Seoul 136-701, Korea (e-mail: seosh77@gmail.com).J. Won, S. Sultana, and E. Bertino are with the Department ofComputer Science, Purdue University, West Lafayette, IN 47907 USA(e-mail: won12@purdue.edu; ssultana@purdue.edu; bertino@purdue.edu).Color versions of one or more of the figures in this paper are availableonline at http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TIFS.2014.2375555on symmetric key encryption [1]–[3]. Such type of encryptionis well-suited for sensor nodes because of their limitedenergy and processing capability. However, it suffers from highcommunication overhead and requires large memory space tostore shared pairwise keys. It is also not scalable and notresilient against compromises, and unable to support nodemobility. Therefore symmetric key encryption is not suitablefor dynamic WSNs. More recently, asymmetric key basedapproaches have been proposed for dynamic WSNs [4]–[7],[10], [15], [18], [25], [27]. These approaches take advantageof public key cryptography (PKC) such as elliptic curvecryptography (ECC) or identity-based public key cryptography(ID-PKC) in order to simplify key establishment anddata authentication between nodes. PKC is relatively moreexpensive than symmetric key encryption with respect tocomputational costs. However, recent improvements in theimplementation of ECC [11] have demonstrated the feasibilityof applying PKC to WSNs. For instance, the implementationof 160-bit ECC on an Atmel AT-mega 128, which has an8-bit 8 MHz CPU, shows that an ECC point multiplicationtakes less than one second [11]. Moreover, PKC is moreresilient to node compromise attacks and is more scalableand flexible. However, we found the security weaknessesof existing ECC-based schemes [5], [10], [25] that theseapproaches are vulnerable to message forgery, key compromiseand known-key attacks. Also, we analyzed the critical securityflaws of [15] that the static private key is exposed to the otherwhen both nodes establish the session key. Moreover, theseECC-based schemes with certificates when directly appliedto dynamic WSNs, suffer from the certificate managementoverhead of all the sensor nodes and so are not a practicalapplication for large scale WSNs. The pairing operationbasedID-PKC [4], [18] schemes are inefficient due to thecomputational overhead for pairing operations. To the best ofour knowledge, efficient and secure key management schemesfor dynamic WSNs have not yet been proposed.In this paper, we present a certificateless effective keymanagement (CL-EKM) scheme for dynamic WSNs. In certificatelesspublic key cryptography (CL-PKC) [12], the user’sfull private key is a combination of a partial private keygenerated by a key generation center (KGC) and the user’s ownsecret value. The special organization of the full private/publickey pair removes the need for certificates and also resolves thekey escrow problem by removing the responsibility for theuser’s full private key. We also take the benefit of ECC keysdefined on an additive group with a 160-bit length as secureas the RSA keys with 1024-bit length.1556-6013 © 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.372 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015In order to dynamically provide both node authenticationand establish a pairwise key between nodes, we buildCL-EKM by utilizing a pairing-free certificateless hybridsigncryption scheme (CL-HSC) proposed by us in an earlierwork [13], [14]. Due to the properties of CL-HSC, thepairwise key of CL-EKM can be efficiently shared betweentwo nodes without requiring taxing pairing operations andthe exchange of certificates. To support node mobility, ourCL-EKM also supports lightweight processes for cluster keyupdates executed when a node moves, and key revocation isexecuted when a node is detected as malicious or leaves thecluster permanently. CL-EKM is scalable in case of additionsof new nodes after network deployment. CL-EKM is secureagainst node compromise, cloning and impersonation, andensures forward and backward secrecy. The security analysisof our scheme shows its effectiveness. Below we summarizethe contributions of this paper:• We show the security weaknesses of existingECC based key management schemes for dynamicWSNs [10], [15], [25].• We propose the first certificateless effective keymanagement scheme (CL-EKM) for dynamic WSNs.CL-EKM supports four types of keys, each of whichis used for a different purpose, including securepair-wise node communication and group-oriented keycommunication within clusters. Efficient key managementprocedures are defined as supporting node movementsacross different clusters and key revocation process forcompromised nodes.• CL-EKM is implemented using Contiki OS and use aTI exp5438 emulator to measure the computation andcommunication overhead of CL-EKM. Also we developa simulator to measure the energy consumption ofCL-EKM. Then, we conduct the simulation of nodemovement by adopting the RandomWalk Mobility Modeland the Manhattan Mobility Model within the grid. Theexperimental results show that our CL-EKM scheme islightweight and hence suitable for dynamic WSNs.The remainder of this paper is organized as follows:In Section 2, we briefly discuss related work and show thesecurity weaknesses of the existing schemes. In Section 3, weprovide our network model and adversary model. In Section 4,we provide an overview of our CL-EKM. In Section 5, weintroduce the details of CL-EKM. In Section 6, we analyzethe security of CL-EKM. In Section 7, we evaluate theperformance of CL-EKM, conduct the simulation of nodemovement in Section 8, and conclude in Section 9.II. RELATED WORKSymmetric key schemes are not viable for mobile sensornodes and thus past approaches have focused only on staticWSNs. A few approaches have been proposed based on PKCto support dynamic WSNs. Thus, in this section, we reviewprevious PKC-based key management schemes for dynamicWSNs and analyze their security weaknesses or disadvantages.Chuang et al. [7] and Agrawal et al. [8] proposed atwo-layered key management scheme and a dynamickey update protocol in dynamic WSNs based on theDiffie-Hellman (DH), respectively. However, bothschemes [7], [8] are not suited for sensors with limitedresources and are unable to perform expensive computationswith large key sizes (e.g. at least 1024 bit). Since ECC iscomputationally more efficient and has a short key length(e.g. 160 bit), several approaches with certificate [5], [10],[15], [25] have been proposed based on ECC. However,since each node must exchange the certificate to establishthe pairwise key and verify each other’s certificate beforeuse, the communication and computation overhead increasedramatically. Also, the BS suffers from the overhead ofcertificate management. Moreover, existing schemes [5], [10],[15], [25] are not secure. Alagheband et al. [5] proposed a keymanagement scheme by using ECC-based signcryption, butthis scheme is insecure against message forgery attacks [16].Huang et al. [15] proposed a ECC-based key establishmentscheme for self-organizing WSNs. However, we found thesecurity weaknesses of their scheme. In step 2 of their scheme,a sensor node U sends z = qU · H(MacKey) + dU (modn)to the other node V for authentication, where qU is astatic private key of U. But, once V receives the z, itcan disclose qU, because V already got MacKey anddU in step 1. So, V can easily obtain qU by computingqU = (z − dU) · H(MacKey)−1. Thus, the sensor node’sprivate key is exposed to the other node during the keyestablishment between two nodes. Zhang et al. [10] proposeda distributed deterministic key management scheme based onECC for dynamic WSNs. It uses the symmetric key approachfor sharing the pairwise key for existing nodes and uses anasymmetric key approach to share the pairwise keys for anew node after deployment. However, since the initial key KIis used to compute the individual keys and the pairwise keysafter deployment for all nodes, if an adversary obtains KI, theadversary has the ability to compute all individual keys andthe pairwise keys for all nodes. Thus, such scheme suffersfrom weak resilience to node compromises. Also, sincesuch scheme uses a simple ECC-based DH key agreementby using each node’s long-term public key and privatekey, the shared pairwise key is static and as a result, isnot secure against known-key attacks and cannot providere-key operation. Du et al. [25] use a ECDSA scheme toverify the identity of a cluster head and a static EC-Diffie-Hellman key agreement scheme to share the pairwise keybetween the cluster heads. Therefore, the scheme by Duet al. is not secure against known-key attacks, because thepairwise key between the cluster heads is static. On the otherhand, Du et al. use a modular arithmetic-based symmetrickey approach to share the pairwise key between a sensornode and a cluster head. Thus, a sensor node cannot directlyestablish a pairwise key with other sensor nodes and, instead,it requires the support of the cluster head. In their scheme, inorder to establish a pairwise key between two nodes in thesame cluster, the cluster head randomly generates a pairwisekey and encrypts it using the shared keys with these twonodes. Then the cluster head transmits the encrypted pairwisekey to each node. Thus, if the cluster head is compromised,the pairwise keys between non-compromised sensor nodesin the same cluster will also be compromised. Therefore,SEO et al.: EFFECTIVE KEY MANAGEMENT IN DYNAMIC WSNs 373Fig. 1. Heterogeneous dynamic wireless sensor network.their scheme is not compromise-resilient against clusterhead capture, because the cluster head randomly generates apairwise key between sensor nodes whenever it is requestedby the nodes. Moreover, in their scheme, in order to share apairwise key between two nodes in different clusters, thesetwo nodes must communicate via their respective clusterheads. So, after one cluster head generates the pairwisekey for two nodes, the cluster head must securely transmitthis key to both its node and the other cluster head. Thus,this pairwise key should be encrypted by using the sharedpairwise key with the other cluster head and the shared keywith its node, respectively. Therefore, if the pairwise keybetween the cluster heads is exposed, all pairwise keys of thetwo nodes in different clusters are disclosed. The scheme byDu et al. supports forward and backward secrecy by using akey update process whenever a new node joins the clusteror if a node is compromised. However, the scheme does notprovide a process to protect against clone and impersonationattack.Most recently, Rahman et al. [4] and Chatterjee et al. [18]have proposed ID-PKC based key management schemessupporting the mobility of nodes in dynamic WSNswhich removes the certificate management overhead.However, their schemes require expensive pairing operations.Although many approaches that enable pairing operations forsensor nodes have been proposed, the computational costrequired for pairing is still considerably higher than standardoperations such as ECC point multiplication. For example,NanoECC, which uses the MIRACL library, takes around17.93s to compute one pairing operation and around 1.27s tocompute one ECC point multiplication on the MICA2(8MHz)mote [17].III. NETWORK AND ADVERSARY MODELSA. Network ModelWe consider a heterogeneous dynamic wireless sensornetwork (See Fig. 1). The network consists of a number ofstationary or mobile sensor nodes and a BS that manages thenetwork and collects data from the sensors. Sensor nodes canbe of two types: (i) nodes with high processing capabilities,referred to as H-sensors, and (ii) nodes with low processingcapabilities, referred to as L-sensors. We assume to haveN nodes in the network with a number N1 of H-sensorsand a number N2 of L-sensors, where N = N1 + N2, andN1 _ N2. Nodes may join and leave the network, and thusthe network size may dynamically change. The H-sensors actas cluster heads while L-sensors act as cluster members. Theyare connected to the BS directly or by a multi-hop path throughother H-sensors. H-sensors and L-sensors can be stationary ormobile. After the network deployment, each H-sensor formsa cluster by discovering the neighboring L-sensors throughbeacon message exchanges. The L-sensors can join a cluster,move to other clusters and also re-join the previous clusters.To maintain the updated list of neighbors and connectivity,the nodes in a cluster periodically exchange very lightweightbeacon messages. The H-sensors report any changes in theirclusters to the BS, for example, when a L-sensor leaves orjoins the cluster. The BS creates a list of legitimate nodes,M, and updates the status of the nodes when an anomalynode or node failure is detected. The BS assigns each nodea unique identifier. A L-sensor nLi is uniquely identified bynode ID Li whereas a H-sensor nHj is assigned a node ID Hj .A Key Generation Center (KGC), hosted at the BS, generatespublic system parameters used for key management by theBS and issues certificateless public/private key pairs for eachnode in the network. In our key management system, a uniqueindividual key, shared only between the node and the BS isassigned to each node. The certificateless public/private keyof a node is used to establish pairwise keys between any twonodes. A cluster key is shared among the nodes in a cluster.B. Adversary Model and Security RequirementsWe assume that the adversary can mount a physical attackon a sensor node after the node is deployed and retrieve secretinformation and data stored in the node. The adversary can alsopopulate the network with the clones of the captured node.Even without capturing a node, an adversary can conduct animpersonation attack by injecting an illegitimate node, whichattempts to impersonate a legitimate node. Adversaries canconduct passive attacks, such as, eavesdropping, replay attack,etc to compromise data confidentiality and integrity. Specificto our proposed key management scheme, the adversary canperform a known-key attack to learn pairwise master keys if itsomehow learns the short-term keys, e.g., pairwise encryptionkeys. As described in [26] and [8], in order to provide a securekey management scheme for WSNs supporting mobile nodes,the following security properties are critical:• Compromise-Resilience: A compromised node must notaffect the security of the keys of other legitimate nodes.In other words, the compromised node must not be ableto reveal pairwise keys of non-compromised nodes. Thecompromise-resilience definition does not mean that anode is resilient against capture attacks or that a capturednode is prevented from sending false data to other nodes,BS, or cluster heads.• Resistance Against Cloning and Impersonation: Thescheme must support node authentication to protectagainst node replication and impersonation attacks.• Forward and Backward Secrecy: The scheme must assureforward secrecy to prevent a node from using an oldkey to continue decrypting new messages. It must alsoassure backward secrecy to prevent a node with the newkey from going backwards in time to decrypt previouslyexchanged messages encrypted with prior keys. forwardand backward secrecy are used to protect against nodecapture attacks.374 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015• Resilience Against Known-Key Attack: The scheme mustbe secure against the known-key attack.IV. OVERVIEW OF THE CERTIFICATELESS EFFECTIVEKEY MANAGEMENT SCHEMEIn this paper, we propose a Certificateless Key Managementscheme (CL-EKM) that supports the establishment of fourtypes of keys, namely: a certificateless public/private key pair,an individual key, a pairwise key, and a cluster key. Thisscheme also utilizes the main algorithms of the CL-HSCscheme [13] in deriving certificateless public/private keys andpairwise keys. We briefly describe the major notations usedin the paper (See Table I), the purpose of these keys and howthey are setup.A. Types of Keys• Certificateless Public/Private Key: Before a node isdeployed, the KGC at the BS generates a uniquecertificateless private/public key pair and installs the keysin the node. This key pair is used to generate a mutuallyauthenticated pairwise key.• Individual Node Key: Each node shares a uniqueindividual key with BS. For example, a L-sensor can usethe individual key to encrypt an alert message sent tothe BS, or if it fails to communicate with the H-sensor.An H-sensor can use its individual key to encrypt themessage corresponding to changes in the cluster. TheBS can also use this key to encrypt any sensitive data,such as compromised node information or commands.Before a node is deployed, the BS assigns the node theindividual key.• Pairwise Key: Each node shares a different pairwise keywith each of its neighboring nodes for secure communicationsand authentication of these nodes. For example, inorder to join a cluster, a L-sensor should share a pairwisekey with the H-sensor. Then, the H-sensor can securelyencrypt and distribute its cluster key to the L-sensorby using the pairwise key. In an aggregation supportiveWSN, the L-sensor can use its pairwise key to securelytransmit the sensed data to the H-sensor. Each nodecan dynamically establish the pairwise key between itselfand another node using their respective certificatelesspublic/private key pairs.• Cluster Key: All nodes in a cluster share a key, named ascluster key. The cluster key is mainly used for securingbroadcast messages in a cluster, e.g., sensitive commandsor the change of member status in a cluster. Only thecluster head can update the cluster key when a L-sensorleaves or joins the cluster.V. THE DETAILS OF CL-EKMThe CL-EKM is comprised of 7 phases: system setup,pairwise key generation, cluster formation, key update, nodemovement, key revocation, and addition of a new node.TABLE ILIST OF NOTATIONSA. System SetupBefore the network deployment, the BS generates systemparameters and registers the node by including it in a memberlist M.1) Generation of System Parameters: The KGC at theBS runs the following steps by taking a security parameterk ∈ Z+ as the input, and returns a list of system parameter_ = {Fq , E/Fq , Gq , P, Ppub = x P, h0, h1, h2, h3} and x.• Choose a k-bit prime q• Determine the tuple {Fq , E/Fq , Gq , P}.• Choose the master private key x ∈R Z∗qand compute thesystem public key Ppub = x P.• Choose cryptographic hash functions {h0, h1,h2, h3} so that h0 : {0, 1}∗ × G2q→ {0, 1}∗, h1 :G3q× {0, 1}∗ × Gq → {0, 1}n, h2 : Gq × {0, 1}∗ ×Gq × {0, 1}∗ × Gq × {0, 1}∗ × Gq → Z∗q, andh3 : Gq×{0, 1}∗×Gq×{0, 1}∗×Gq×{0, 1}∗×Gq → Z∗q.Here, n is the length of a symmetric key.The BS publishes _ and keeps x secret.2) Node Registration: The BS assigns a unique identifier,denoted by Li , to each L-sensor nLi and a unique identifier,denoted by Hj , to each H-sensor nHj, where 1 ≤ i ≤ N1,1 ≤ j ≤ N2, N = N1 + N2. Here we describe the certificatelesspublic/private key and individual node key operationsfor Li , the same mechanisms apply for H-sensors. Duringinitialization, each node nLi chooses a secret value xLi∈R Z∗qand computes PLi= xLi P. Then, the BS requests the KGCfor partial private/public keys of nLi with the input parametersLi and PLi. The KGC chooses rLi∈R Z∗qand then computesa pair of partial public/private key (RLi , dLi ) as below:RLi= rLi PdLi= rLi+ x · h0(Li , RLi , PLi ) mod qThe Li can validate its private key by checking whetherthe condition dLi P = RLi+ h0(Li , RLi , PLi )Ppub holds.SEO et al.: EFFECTIVE KEY MANAGEMENT IN DYNAMIC WSNs 375Li then sets skLi= (dLi , xLi ) as its full private key andpkLi= (PLi , RLi ) as its full public key. The BS also choosesa uniform random number x0 ∈ Z∗qto generate the node’sindividual key K0Li(K0Hjfor nHj ). The individual key iscomputed as an HMAC of x0, Li as followsK0Li= HMAC(x0, Li )After the key generation for all the nodes, the BS generatesa member list M consisting of identifiers and public keysof all these nodes. It also initializes a revocation list R thatenlists the revoked nodes. The public/private key, _, and theindividual key are installed in the memory of each node.B. Pairwise Key GenerationAfter the network deployment, a node may broadcast anadvertisement message to its neighborhood to trigger thepairwise key setup with its neighbors. The advertisementmessage contains its identifier and public key. At first, twonodes set up a long-term pairwise master key between them,which is then used to derive the pairwise encryption key. Thepairwise encryption key is short-term and can be used as asession key to encrypt sensed data.1) Pairwise Master Key Establishment: In this paragraph,we describe the protocol for establishing a pairwise master keybetween any two nodes nA and nB with unique IDs A and B,respectively.We utilize the CL-HSC scheme [13] as a buildingblock. When nA receives an advertisement message from nB,it executes the following encapsulation process to generate along-term pairwise master key KAB and the encapsulated keyinformation, ϕA = (UA,WA).• Choose lA ∈R Z∗qand compute UA = lAP.• ComputeTA = lA · h0(B, RB, PB)Ppub + lA · RB mod qKAB = h1(UA, TA, lA · PB, B, PB)• Computeh = h2(UA, τA, TA, A, PA, B, PB)h_ = h3(UA, τA, TA, A, PA, B, PB)WA = dA + lA · h + xA · h_where τA is a random string to give a freshness.• Output KAB and ϕA = (UA,WA).Then, nA sends A, pkA, τA and ϕA to nB. nB then performsdecapsulation to obtain KAB.• Compute TA = dB · UA.Note: Because of dB = rB + x · h0(B, RB, PB) andUA = lAP mod q, TA is computed as TA = (rB + x ·h0(B, RB, PB)) · lAP mod q = lA · h0(B, RB, PB)Ppub +lA · RB mod q,• Compute h = h2(UA, τA, TA, A, PA, B, PB) andh_ = h3(UA, τA, TA, A, PA, B, PB).• If WA · P = RA +h0(A, RA, PA) · Ppub +h ·UA +h_ · PA,output KAB = h1(UA, TA, xB · UA, B, PB). Otherwise,output invalid.TABLE IICLUSTER FORMATION PROCESS2) Pairwise Encryption Key Establishment: OncenA and nB set the pairwise master key KAB, they generatean HMAC of KAB and a nonce r ∈R Z∗q. The HMAC is thenvalidated by both nA and nB. If the validation is successful,the HMAC value is established as the short-term pairwiseencryption key kAB. The process is summarized below:• nB chooses a random nonce r ∈R Z∗q, computeskAB = HMAC(KAB, r ) and C1 = EkAB (r, A, B). Then,nB sends r and C1 to nA.• When nA receives r and C1, it computeskAB = HMAC(KAB, r ) and decrypts C1. Then itvalidates r , A and B and if valid confirms that nB knowsKAB and it can compute kAB.C. Cluster FormationOnce the nodes are deployed, each H-sensor discoversneighboring L-sensors through beacon message exchanges andthen proceeds to authenticate them. If the authentication issuccessful, the H-sensor forms a cluster with the authenticatedL-sensors and they share a common cluster key. TheH-sensor also establishes a pairwise key with each memberof the cluster. To simplify the discussion, we focus on theoperations within one cluster and consider the j th cluster.We also assume that the cluster head H-sensor is nHj withnLi (1 ≤ i ≤ n) as cluster members. nHj establishes a clusterkey GKj for secure communication in the cluster. Table IIshows the cluster formation process.1) Node Discovery and Authentication: For node discovery,nHj broadcasts an advertisement message containingHj and pkHj. Once nLi within Hj ’s radio range receivesthe advertisement, it checks Hj and pkHj , and initiatesthe Pairwise Key Generation procedure. Note that nLi mayreceive multiple advertisement messages if it is within therange of more than one H-sensor. However, nLi must chooseone H-sensor, may be by prioritizing over the proximity andsignal strength. Additionally, nLi can record other H-sensoradvertisements as backup cluster heads in the event that theprimary cluster head is disabled. If nLi selects multiple clusterheads and sends a response to all of them, it is considered as376 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015a compromised node. nLi and nHj perform the Pairwise KeyGeneration procedure to obtain a pairwise master key, KLi Hjand a pairwise encryption key, kLi Hj .2) Cluster Key Generation: nHj chooses x j ∈R Z∗qtogenerate a cluster key GKj as followsGKj = HMAC(x j , Hj )Then, nHj computes C2 = EkLi Hj(GKj , Hj , Li ) to distributethe GKj. Then nHj sends Hj and C2 to nLi . nLi decryptsC2 to recover Hj , Li and GKj by using kLi Hj . If nLi fails tocheck Hj , Li , it discards the message and reports nHj to theBS as an illegitimate cluster head. Otherwise, nLi confirms thatnHj is valid and can compute GKj . Then, nLi stores GKj asa cluster key. Next, nLi computes HMAC(kLiHj ,GKj ) andC3 = EkLi Hj(Li ,HMAC(kLi Hj ,GKj )). It transmits C3 andLi to nHj. After nHj receives messages from nLi , it decryptsC3 by using kLi Hj . Then it checks Li and the validity ofHMAC(kLiHj ,GKj ). If the validity check fails, nHj discardsthe message. Otherwise, nHj can confirm that nLi shares thevalid GKj and kHj Li . nHj adds Li and pkLi on member listof the j th cluster, Mj .3) Membership Validation: After discovering all the neighboringnodes nLi (1 ≤ i ≤ n) in the j th cluster, nHj computesC4 = EK0Hj(Hj ,Mj ) and transmits C4 and Hj to the BS.After receiving messages from nHj , the BS checks the validityof the nodes listed in Mj . If all nodes are legitimate, the BSsends an acknowledgement to nHj . Otherwise, the BS rejectsMj and investigates the identities of invalid nodes (false orduplicate ID). Then, the BS adds the identities of invalid nodesto the revocation list and reports it to nHj . Upon receiving theacknowledge message, nHj computes C5 = EGKj (Hj ,Mj )and broadcasts C5 to all the nodes in j th cluster.D. Key UpdateIn order to protect against cryptanalysis and mitigatedamage from compromised keys, frequent encryption keyupdates are commonly required. In this section we providethe pairwise key update and cluster key update operations.1) Pairwise Key Update: To update a pairwise encryptionkey, two nodes which shared the pairwise key perform aPairwise Encryption Key Establishment process. On the otherhand, the pairwise master key does not require periodicalupdates, because it is not directly used to encrypt each sessionmessage. As long as the nodes are not compromised, the pairwisemaster keys cannot be exposed. However, if a pairwisemaster key is modified or needs to be updated according tothe policy of the BS, the Pairwise Master Key Establishmentprocess must be executed.2) Cluster Key Update: Only cluster head H-sensors canupdate their cluster key. If a L-sensor attempts to changethe cluster key, the node is considered a malicious node.The operation for any j th cluster is described as follows:1) nHj chooses x_j∈R Z∗qand computes a new cluster keyGK_j= HMAC(x_j , Hj ). nHj also generates an Updatemessage including HMAC(GK_j ,Update) and computesC6 = EGKj (GK_j ,HMAC(GK_j ,Update)). Then, nHjtransmits Update and C6 to its cluster members.2) Each member nLi decrypts C6 using the GKj , verifiesHMAC(GK_j ,Update) and updates a cluster key as GK_j .Then, each nLi sends the acknowledgement message to nHj .E. Node MovementWhen a node moves between clusters, the H-sensorsmust properly manage the cluster keys to ensure theforward/backward secrecy. Thus, the H-sensor updates thecluster key and notifies the BS of the changed node status.Through this report, the BS can immediately update the nodestatus in the M. We denote a moving node as nLm .1) Node Leave: A node may leave a cluster due to nodefailure, location change or intermittent communication failure.There are both proactive and reactive ways for the cluster headto detect when a node leaves the cluster. The proactive caseoccurs when the node nLm actively decides to leave the clusterand notifies the cluster head nHj or the cluster head decidesto revoke the node. Since in this case nHj can confirm that thenode has left, it transmits a report EK0Hj(NodeLeave, Lm) toinform the BS that nLm has left the cluster. After receivingthe report, the BS updates the status of nLm in M and sendsan acknowledgement to nHj . The reactive case occurs whenthe cluster head nHj fails to communicate with nLm. It mayhappen that a node dies out of battery power, fails to connectto nHj due to interference or obstacles, is captured by theattacker or is moved unintentionally. Since the nodes in acluster periodically exchange lightweight beacon messages,nHj can detect a disappeared node nLm when it does notreceive the beacon message from nLm for a predeterminedtime period. So, nHj reports the status of the node nLmto the BS by sending EK0Hj(NodeDisappear, Lm). Whenthe BS receives the report, it updates the status of nLm inthe M and acknowledges to nHj. Once nHj receives theacknowledgement from the BS, it changes its cluster keywith the following operations: 1) nHj chooses a new clusterkey GK_j and computes EkLi Hj(GK_j , NodeLeave, Lm) usingpairwise session keys with each node in its cluster, except nLm .2) Then, nHj sends EkLi Hj(GK_j , NodeLeave, Lm) to eachmember node except nLm . 3) Each nLi decrypts it using kLi Hjand updates the cluster key as GK_j .2) Node Join: Once the moving node nLm leaves a cluster,it may join other clusters or return to the previous cluster aftersome period. For the sake of simplicity, we assume that nLmwants to join the lth cluster or return to the j th cluster.(i) Join a New Cluster: nLm sends a join request whichcontains Ln+1 and pkLn+1 to join a lth cluster. After nHlreceives the join request, nLm and nHl perform PairwiseKey Generation procedure to generate KLm Hl and kLm Hl ,respectively. Next, nHl transmits EK0Hl(NodeJoin, Lm)to the BS. The BS decrypts the message and validateswhether nLm is a legitimate node or not and sends anacknowledgement to nHl if successful. The BS alsoupdates the node member list, M. In case of nodevalidation failure at the BS, nHl stops this processand revokes the pairwise key with nLm. Once nHlSEO et al.: EFFECTIVE KEY MANAGEMENT IN DYNAMIC WSNs 377receives the acknowledgement, it performs the ClusterKey Update process with all other nodes in the cluster.nHl also computes EkLm Hl(GK_l , Hl , Lm), and sends itto the newly joined node nLm .(ii) Return to the Previous Cluster: nLm sends a join requestwhich contains Ln+1 and pkLn+1 to join a j th cluster.Once nHj receives the join request, it checks a timerfor nLm which is initially set to the Thold . Thold indicatesthe waiting time before discarding the pairwise masterkey when a L-sensor leaves. If nLm returns to the j thcluster before the timer expires, nLm and nHj performonly the Pairwise Encryption Key Establishment procedureto create a new pairwise encryption key, k_LmHj.Otherwise, they perform the Pairwise Key Generationprocedure to generate a new K_LmHland k_LmHl, respectively.Then, the cluster head nHj also updates the clusterkey to protect backward key secrecy. Before updatingthe cluster key, nHj transmits EK0Hj(NodeReJoin, Lm)to the BS. Once the BS decrypts the message anddetermines that nLm is a valid node, the BS sends theacknowledgement to nHl . The BS then updates the memberlist M. Once nHl receives the acknowledgement,it performs the Cluster Key Update process with allother nodes in the cluster. Afterwards, nHj computesEk_Lm Hj(GK_j , Hj , Lm) and sends it to nLm .F. Key RevocationWe assume that the BS can detect compromisedL-sensors and H-sensors. The BS may have an intrusiondetection system or mechanism to detect malicious nodes oradversaries [19], [20]. Although we do not cover how the BScan discover a compromised node or cluster head in this paper,the BS can utilize the updated node status information of eachcluster to investigate an abnormal node. In our protocol, acluster head reports the change of its node status to the BS,such as whenever a node joins or leaves a cluster. Thus, the BScan promptly manage the node status in the member list, M.For instance, the BS can consider a node as compromisedif the node disappears for a certain period of time. In thatcase, the BS must investigate the suspicious node and itcan utilize the node fault detection mechanism introducedin [21] and [22]. In this procedure, we provide a key revocationprocess to be used when the BS discovers a compromised nodeor a compromised cluster head. We denote a compromisednode by nLc in the j th cluster for a compromise node caseand a compromised head by nHj for a compromise clusterhead case.1) Compromised Node: The BS generates a CompNodemessage and a EK0Hj(CompNode, Lc). Then it sendsEK0Hj(CompNode, Lc) to all nHj , (1 ≤ j ≤ N2). After allH-sensors decrypt the message, they update the revocationlist of their clusters. Then, if related keys with nLc exist, therelated keys are discarded. Other than nLc , nHj performs theNode leave operations to change the current cluster key withthe remaining member nodes.2) Compromised Cluster Head: After the BS generates aCompHeader message and a EK0Li(CompHeader, Hj), itsends the message to all nLi (1 ≤ i ≤ n) in the j th cluster. TheBS also computes EK0Hi(CompHeader, Hj), (1 ≤ i ≤ N2,i _= j ) and transmits it to all H-sensors except nHj. Onceall nodes decrypt the message, they discard the related keyswith nHj . Then, each nLi attempts to find other neighboringcluster heads and performs the Join other cluster steps of theNode join process with the neighboring cluster head. If somenode nLi is unable to find another cluster head node, it mustnotify the BS by sending EK0Li(FindNewClusteLi ). The BSproceeds to find the nearest cluster head nHn for nLi andconnect nHn with nLi . Then, they can perform the Join othercluster steps.G. Addition of a New NodeBefore adding a new node into an existing networks, theBS must ensure that the node is not compromised. Thenew node nLn+1 establishes a full private/public key throughthe node registration phase. Then, the public systemparameters, a full private/public key and individualkey K0Ln+1are stored into nLn+1 . The BS generatesEK0Hj(NewNode, Ln+1, pkLn+1) and sends it to all nHj ,(1 ≤ j ≤ N2). After nLn+1 is deployed in the network,it broadcasts an advertisement message which containsLn+1 and pkLn+1 to join a neighboring cluster. If multipleH-sensors receive nLn+1’s message, they will transmit aResponse message to nLn+1 . nLn+1 must choose one H-sensorfor a valid registration. If nLn+1 selects nHj according to thedistance and the strength of signal, it initiates the PairwiseKey Generation procedure. In order to provide backwardsecrecy, nHj performs Cluster Key Update procedure, wherethe Update message contains Ln+1 and pkLn+1. Then, nHjcomputes C7 = EkLn+1 Hj(GK_j , Hj , Ln+1), and sends C7and Hj to nLn+1. After nLn+1’s registration, nHj transmitsEK0Hj(NodeJoin, Ln+1) to the BS. Once the BS decrypts themessage, it updates the status of the node nLn+1 in memberlist, M.VI. SECURITY ANALYSISFirst, we briefly discuss the security of CL-HSC [13]which is utilized as a building block of CL-EKM. Later,we discuss how CL-EKM achieves our security goals. TheCL-HSC [13] provides both confidentiality and unforgeabilityfor signcrypted messages based on the intractability of theEC-CDH1 Moreover, it is not possible to forge or expose thefull private key of an entity based on the difficulty of EC-CDH,without the knowledge of both KGC’s master private key andan entity’s secret value. Here, the confidentiality is definedas indistinguishability against adaptive chosen ciphertext andidentity attacks (IND-CCA2) while unforgeability is defined1The Elliptic Curve Computational Diffie-Hellman problem (EC-CDH) isdefined as follows: Given a random instance (P,aP, bP) ∈ Gq for a,b ∈R Z∗q, compute abP.378 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015as existential unforgeability against adaptive chosen messagesand identity attacks (EUF-CMA). Further details on theCL-HSC scheme and its security proof are provided in [13].A. Compromise-Resilience of CL-EKMWe assume that an adversary captures a node nLi in thej th cluster. This adversary can then extract the keys of nLi ,such as the pairwise key shared with the cluster head nHj ,the public/private key pair, the cluster key GKj, and theindividual key. However, the pairwise master/encryption keygeneration between any two nodes are independent of others,and hence each pair of nodes has different pairwise keys.Therefore, even if the adversary manages to obtain nLi’s keys,it is unable to extract any information useful to compromisethe pairwise keys of other uncompromised nodes. Moreover,due to the intractability of EC-CDH problem, the adversarycannot obtain the KGC’s master private key x from nLi’spublic/private keys pkLi /skLi . As a result, the compromiseof a sensor does not affect the communication security amongother L-sensors or H-sensors. Even though the attacker canread the group communications within the cluster with thecluster key extracted from the compromised node, it cannotget any information about the cluster key of other clusters.B. Resistance Against Cloning and Impersonation AttackAn adversary can conduct the cloning attack if a node iscaptured; the key is then extracted and the node is replicatedin another neighborhood. However, since the cluster headvalidates each node with the BS in the node join process ofour CL-EKM, the BS is able to detect a cloned node when itis placed in an unintended cluster. After the BS investigatesthe cloned node, it revokes the node and notifies the noderevocation to all cluster heads. Thus, although the cloned nodemay try to join other clusters, the cluster head will abort eachattempt. Therefore, our scheme is resistant against the cloningattack.The adversary may also attempt an impersonation attackby inserting an illegitimate node nC. Assume that a node nCposes as nLi . The node ID Li and public key, pkLi=(PLi , RLi ) are publicly known within the network. Hence,nC can broadcast Li and pkLi. When nL j receives themessage, it will compute the pairwise master key KLi L j ,and the encapsulated key information ϕL j= (UL j ,WL j )towards establishing the pairwise Master key. As the next step,nL j sends ϕL j , L j , pkL j to nC for decapsulation, whichrequires nC to compute TL j as (dLi· UL j ). However, nCfails to compute TL j since nC has no knowledge of nLi’spartial private key dLi . Moreover due to the intractability ofEC-CDH1, the adversary cannot forge dLi without the knowledgeof the KGC’s master private key. Thus, nC is unableto generate a legitimate pairwise master key, KLi L j. However,nC may try to establish the pairwise encryption with a randomkey K_, rather than generating a legitimate master key. To thisend, nC chooses a random nonce r , computes an encryptionkey k_ as HMAC(r, K_) and sends r, E_k (r, Li , L j ) to nL j .However, nC cannot successfully pass the validation at nL j ,since nL j first computes the pairwise encryption key withnL j as kLi L j= HMAC(r, KLi L j ) and then tries to decryptE_k (r, Li , L j ) using kLi L j . Thus, nL j fails to decrypt andhence, it does not confirm the pairwise encryption key to nC,which is then reported to the BS. Thus, CL-EKM is resistantagainst impersonation attacks.C. Forward and Backward SecrecyIn CL-EKM, messages exchanged between nodes or withina cluster are encrypted with the pairwise encryption key orcluster key. CL-EKM provides the key update and revocationprocesses to ensure forward secrecy when a node leaves orcompromised node is detected. Using key update process,CL-EKM ensures backward secrecy when a new node joins.Once a node is revoked from the network, all its keys areinvalidated and the associated cluster key is updated. Thecluster head sends the new cluster key to each cluster node,except the revoked node, by encrypting the key with thepairwise encryption key between the cluster and each intendednode. Thus, the revoked node fails to decrypt any subsequentmessages using the old pairwise encryption key or cluster key.When a node joins a cluster, the cluster head generates a newcluster key by choosing a new random value. Since the joinednode receives the new cluster key, it cannot decrypt earliermessages encrypted using the older cluster keys.D. Resistance Against Known-Key AttackWe assume that an adversary obtains the current pairwiseencryption key kLi Hj= HMAC(KLi Hj , r ) betweennLi and nHj and conducts the known-key attack. The adversarymay attempt to extract the long term pairwise master keyKLi Hj using kLi Hj . However, due to the one-way featureof HMAC(.), the adversary fails to learn KLi Hj. Also,when nLi and nHj update the pairwise encryption key ask_Li Hj= HMAC(KLi Hj , r _), the adversary cannot computethe updated pairwise encryption key k_Li Hj, without the knowledgeof KLi Hj . Thus, CL-EKM is resistant against known-keyattack when the pairwise encryption key is compromised.VII. PERFORMANCE EVALUATIONWe implemented CL-EKM in Contiki OS [29] andused Contiki port [28] of TinyECC [24] for elliptic curvecryptography library. In order to evaluate our scheme, weuse the Contiki simulator COOJA. We run emulations on thestate-of-the-art sensor platform TI EXP5438 which has 16-bitCPU MSP430F5438A with 256KB flash and 16KB RAM.MSP430F5438A has 25MHz clock frequency and can belowered for power saving.A. Performance Analysis of CL-EKMWe measure the individual performance of the three stepsin the pairwise master/encryption key establishment process,namely, (i) encapsulation, (ii) decapsulation, and (iii) pairwiseencryption key generation. We evaluate each step in termsof (i) computation time, and (ii) energy consumption.In this experiment, we vary the processing power i.e. CPUclock rate of the sensors since we consider heterogeneousSEO et al.: EFFECTIVE KEY MANAGEMENT IN DYNAMIC WSNs 379Fig. 2. Computation overhead for pairwise master/encryption key establishment. (a) Encapsulating key information. (b) Decapsulating key information.(c) Pairwise encryption key establishment.Fig. 3. Energy consumption for pairwise master/encryption key establishment. (a) Encapsulating key information. (b) Decapsulating key information.(c) Pairwise encryption key establishment.WSNs with H-sensors being more powerful. Three differentelliptic curves recommended by SECG (Standards for EfficientCryptography Group) [30], i.e., (i) secp128r2 (128-bit ECC),(ii) secp160r1 (160-bit ECC), and (iii) secp192r1 (192-bitECC), are used for the experiment.Fig. 2 shows the time for the pairwise key generationprocess. As expected, the pairwise master key generationtakes most of the time due to the ECC operations(See Fig. 2(a), 2(b)). However, it is important to mention thatthe pairwise master key is used only to derive the short-termpairwise encryption key. Once two nodes establish the pairwisekeys, they do not require further ECC operations. Fig. 2(a)shows the computation times of the encapsulation process forvarious CPU clock rates of the sensor device. The computationtime increases with the ECC key bit length. secp192r1 needsalmost 1.5 times more time than secp160r1. secp128r2 takesapproximately 4% less time than secp160r1. If CPU clockrate is set to 25MHz and secp160r1 is adopted, 5.7 secondsare needed for encapsulation of key. Fig. 2(b) shows theprocessing time for the decapsulation. Decapsulation requiresabout 1.57 times more CPU computation time than encapsulation.This is because decapsulation has six ECC pointmultiplications, whereas encapsulation includes only four ECCpoint multiplications. Finally, the computation time for pairwiseencryption key establishment is shown in Fig. 2(c).At 25MHz CPU clock rate, it requires 5 ms, which is negligiblecompared to the first two steps. This is due to the factthat this step just needs one HMAC and one 128-bit AESoperation. Next, we measure the energy consumption. As wecan see from Fig. 3, the faster the processing power (i.e. CPUclock rate) is, the more energy is consumed. However, asshown in Fig. 3(a) and Fig. 3(b), there is no differencebetween 16MHz and 25MHz while 25MHz results in fastercomputation than 16MHz. In addition, secp160r1 might bea good choice for elliptic curve selection, since it is moresecure than secp128r2 and consumes reasonable CPU timeand energy for WSNs. In our subsequent experiments, weutilize secp160r1.B. Performance ComparisonsIn this section, we benchmark our scheme with three previousECC-based key management schemes for dynamic WSNs:HKEP [15], MAKM [25] and EDDK [10]. Due to the variabilityof every schemes, we chose to compare a performance ofthe pairwise master key generation step because it is the mosttime consuming portion in each of the schemes. We measuredthe total energy consumption of computation and communicationto establish a pairwise key between two L-sensors. Forthe experiment, we implemented four schemes on TI EXP5438at 25MHz using ECC with secp160r1 parameters andAES-128 symmetric key encryption. EC point is compressedto reduce the packet size and LPL (Low Power Listening)is utilized for power conservation. Thus, sensors wake upfor short durations to check for transmissions every second.If no transmission is detected, they revert to a sleep mode.To compute the energy consumption for communication, weutilize the energy consumption data of CC2420 from [27]and IEEE 802.15.4 protocol overhead data from [31]. We considertwo scenarios as shown in Fig. 4. In the first scenario,two L-sensors lie within a 1-hop range, but the distancebetween the H-sensor and the L-sensor varies from 1 to 8(see Fig. 4 (a)). In the second scenario, two L-sensors andthe H-sensor lie in a 1-hop range, but the wireless channelconditions are changed (see Fig. 4 (b)). When a wirelesschannel condition is poor, a sender may attempt to resend apacket to a destination multiple times. Expected TransmissionCount (ETX) is the expected number of packet transmissionto be received at the destination without error. Fig. 5shows the energy consumption of the four schemes for apairwise key establishment when the number of hops betweenL-sensors and H-sensor, n, increases. When n is one, HKEP380 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015Fig. 4. Network topology.Fig. 5. Energy consumption comparison for pairwise key establishment inscenario (a).requires more energy than our scheme because it performs sixmessage exchanges to establish a pairwise key between twoL-sensors, while our scheme needs just two messageexchanges. When n is one, MAKM consumes the leastenergy because the L-sensor performs a single AESsymmetric encryption, but other schemes run expensive ECCoperations. However, as n increases, the energy of MAKMincreases because the H-sensor is always involved in thegeneration of a pairwise key between two L-sensors. As aresult, MAKM consumes more energy than our scheme whenn is larger than one and the gap also widens when n increases.A packet delivery in a wireless sensor network is unreliabledue to unexpected obstacles, time-varying wireless channelconditions, and a low-power transceiver. Fig. 6 shows theenergy consumption of the four schemes for a pairwisekey establishment when ETX varies from 1 to 4. As ETXincreases, the energy consumption of HKEP increases morerapidly, because it requires six message exchanges. Also,HKEP is insecure, because the static private key of a nodeis exposed to the other node while the two nodes establishthe session key. Although EDDK and MAKM may showbetter performance due to low computational overhead, thedifference between MAKM and our scheme is only 0.121 Jand the difference between EDDK and our scheme is 0.045 J.Both EDDK and MAKM are insecure against the knownkeyattack and do not provide a re-keying operation for thecompromised pairwise key. EDDK also suffers from weakresilience to node compromises. Therefore, this performanceevaluation demonstrates that overall, our scheme outperformsthe existing schemes in terms of a better trade-off between thedesired security properties and energy consumption includingcomputational and communication overhead.VIII. SIMULATION OF NODE MOVEMENTSA. SettingWe developed a simulator which counts the keymanagement-related events and yields total energy consumptionfor key-management-related computations using the datain Sec. 7.1. We focus on the effects of node movement andFig. 6. Energy consumption comparison for pairwise key establishment inscenario (b).Fig. 7. Network topology for simulation.do not consider the impact of lower network layer protocols.We consider a 400×400 m2 space with 25 H-sensors placedon the grid corners (see Fig. 7). In CL-EKM, an H-sensormaintains two timers: Tbackof f and Thold to efficiently managethe cluster when a node moves. Tbackof f denotes the clusterkey update frequency. If Tbackof f = 0, the cluster key isupdated whenever a node joins or leaves. Otherwise, theH-sensor waits a time equal to Tbackof f after a node joinsor leaves to update the cluster key. Thold denotes the waitingtime before discarding the pairwise master key when aL-sensor leaves. If Thold = 0, the pairwise master key witha L-sensor is revoked right after the node leaves the cluster.Otherwise, the H-sensor stores the pairwise master key withthe left L-sensor for a time equal to Thold . For the movementof L-sensor, we adopt two well-known mobility models usedfor simulation of mobile ad-hoc network: the Random WalkMobility Model and the Manhattan Mobility Model [32].H-sensors are set to be stationary since they are usually partof the static infrastructure in real world applications.1) Random Walk Mobility Model: The Random WalkMobility Model mimics the unpredictable movements of manyobjects in nature. In our simulation, 1,000 L-sensors arerandomly distributed. Each L-sensor randomly selects anH-sensor among the four H-sensors in its vicinity and establishesthe pairwise key and cluster key. After the simulationstarts, the L-sensors randomly select a direction and moveat a random speed uniformly selected from [0, 2VL] (i.e., themean speed = VL ). The new direction and speed are randomlyselected every second. If a L-sensor crosses a line, it firstchecks whether it is still connected with its current H-sensor.If not, the node attempts to find an H-sensor which it hadSEO et al.: EFFECTIVE KEY MANAGEMENT IN DYNAMIC WSNs 381Fig. 8. Node movement simulation results in random walk mobility model. (a) Energy consumption of one H-sensor for cluster key update for one day(Thold = 100 sec). (b) Energy consumption of one H-sensor for pairwise key establishment for one day (Tbacko f f = 6 sec). (c) Energy consumption of oneL-sensor for pairwise key establishment for one day (Tbacko f f = 6 sec).Fig. 9. Node movement simulation results in Manhattan mobility model. (a) Energy consumption of one H-sensor for cluster key update for one day(Thold = 100 sec). (b) Energy consumption of one H-sensor for pairwise key establishment for one day (Tbacko f f = 6 sec). (c) Energy consumption of oneL-sensor for pairwise key establishment for one day (Tbacko f f = 6 sec).previously connected to and it still maintains a pairwise masterkey. In the case of a failure, the node randomly selects anH-sensor among the surrounding H-sensors.2) Manhattan Mobility Model: The Manhattan MobilityModel mimics the movement patterns in an urban area organizedaccording to streets and roads. In our simulation, 1,000L-sensors are randomly distributed and move in a grid. Theycan communicate with two adjacent H-sensors. Each L-sensorrandomly selects its direction and chooses an H-sensor withinits path as its cluster head. After the simulation starts, theL-sensors move at a random speed uniformly selected from[0, 2VL]. At each intersection, a L-sensor has 0.5 probabilityof moving straight and a 0.25 probability of turning left orright. If a L-sensor arrives at a new intersection, it first choosesa new direction and checks whether it is still connected withits current H-sensor. If not, it chooses an H-sensor within itsnew vector as its new cluster head.B. The Effect of Tbackof fFig. 8(a) shows the energy consumption of an H-sensorfor a cluster key update during the course of a day ina Random Walk Model. As Tbackof f increases, the energyconsumption decreases since the number of cluster key updatesis reduced. The faster VL is, the more rapidly the energyconsumption decreases as Tbackof f increases since L-sensorsfrequently cross the border lines. This tendency also showsin the Manhattan Mobility Model (see Fig. 9(a)). However,the H-sensors consume more energy at low speeds than inthe Random Walk Mobility Model since the L-sensors do notchange directions until they reach an intersection. A largerTbackof f means a lower security level. Thus, there is a tradeoffbetween the security level and the energy consumption ofthe H-sensor. However, at high speeds, i.e., 16 m/s, Tbackof fshould be less than 1 second since the number of cluster keyupdates is minimal when Tbackof f is greater than 1 second.However, at low speeds, 1, 2 or 3 seconds are a reasonablechoice for the H-sensors.C. The Effect of TholdFig. 8(b) and Fig. 8(c) show the energy consumption of oneH-sensor and one L-sensor for a pairwise key establishmentin the Random Walk Mobility Model over the course of aday, respectively. The effect of Thold increases as the nodevelocity increases. As Thold increases, the energy consumptiondecreases because in the event that the L-sensors return to theold clusters before the timers expire, no new pairwise masterkey establishment is necessary. As shown in Table III theenergy differences caused by node velocity and Thold is due tothe differences in the frequency of pairwise key establishment.Such frequency is linearly proportional to velocity increases.When Thold ranges from 0 to 500 seconds, energy consumptionrapidly decreases because several moving nodes may return totheir previous clusters within the 500 seconds. However, whenThold ranges from 500 to 1,500 seconds, the energy consumptiondecreases more slowly since the probability of nodesreturning to their previous clusters is dramatically reduced.In the Manhattan Mobility Model, when Thold is small, moreenergy is consumed than in the Random Walk Mobility Modelduring pairwise key establishment since the L-sensors returnto their previous clusters with low frequency. (see Fig. 9(b) andFig. 9(c)). However, when Thold is large, the energy consumedfor the pairwise key establishment dramatically decreases.For instance, as shown in Table IV, when the node speedis 16 m/s and Thold is 1,000 seconds, the number of pairwisekey establishments is only 24,418 which is 5.4 times smaller382 IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 10, NO. 2, FEBRUARY 2015TABLE IIITHE FREQUENCY OF PAIRWISE KEY ESTABLISHMENTS FORONE DAY IN RANDOM WALK MOBILITY MODELTABLE IVTHE FREQUENCY OF PAIRWISE KEY ESTABLISHMENTS FORONE DAY IN MANHATTAN MOBILITY MODELthan in the Random Walk Mobility Model with the samesettings.Similarly to Tbackof f , a larger Thold means a lower securitylevel. Thus, Thold should be selected according to VL, energyconsumption amount, and the desired security level. Resultsfrom Fig. 8(c) and Fig. 9(c) show that our scheme is practicalfor real-world monitoring applications such as in animaltracking or traffic monitoring. For example, L-sensors movingat 1 m/s in the Random Walk Mobility Model only use at most0.67 J per day if Thold is greater than 100 seconds. Also,L-sensors moving at 16 m/s in the Manhattan Mobility Modelonly use at most 1.16 J per day if Thold is greater than1,000 seconds. Considering that the average energy of oneC-size alkaline battery is 34,398 J [23], the energyconsumption of the L-sensor for a pairwise key establishmentis relatively small.IX. CONCLUSIONS AND FUTURE WORKSIn this paper, we propose the first certificateless effective keymanagement protocol (CL-EKM) for secure communication indynamic WSNs. CL-EKM supports efficient communicationfor key updates and management when a node leaves or joinsa cluster and hence ensures forward and backward key secrecy.Our scheme is resilient against node compromise, cloningand impersonation attacks and protects the data confidentialityand integrity. The experimental results demonstrate the efficiencyof CL-EKM in resource constrained WSNs. As futurework, we plan to formulate a mathematical model for energyconsumption, based on CL-EKM with various parametersrelated to node movements. This mathematical model will beutilized to estimate the proper value for the Thold and Tbackof fparameters based on the velocity and the desired tradeoffbetween the energy consumption and the security level.