一种基于Shamir的安全WSN分簇路由协议设计*

戴国勇，吕何新，丁健龙，赵 方，毛科技，彭 丰

(1.浙江树人大学信息科技学院，浙江 杭州 310015；2.浙江工业大学计算机科学与技术学院，浙江 杭州 310023；3.衢州华数广电网络有限公司，浙江 衢州 324000)

无线传感器网络(Wireless Sensor Networks，WSNs)是物联网的一项重要技术，由大量具有计算能力、通信能力和数据处理能力的传感器节点，通过无线自组织的形式构成的网络[1-2]。路由技术是无线传感器网络除节点定位、网络覆盖、能量管理和隐私保护等问题外的一个重要研究方向[3]。一种良好的路由技术能够提供可靠的数据转发、较好的能耗均衡以及安全的数据路由[4]。由于传感器网络部署的环境复杂，传感器节点更换电池困难，当节点负载不均衡时，负载大的节点消耗的能量多，死亡较快，从而导致网络过早失效。在无线传感器网络中，恶意节点可伪装成网络内的成员节点破坏网络或者窃取网络数据，给WSN带来安全威胁，因此路由协议设计时需考虑数据安全性。

无线传感器网络路由协议主要分为两种，一种是链式路由协议，另一种是层次路由协议[5]。其中链式路由协议在数据流量较大时容易导致链路拥塞，因此适合应用于小规模的网络中。而层次路由协议是一种划分区域的路由协议，适用于大规模的网络。分簇路由协议作为层次路由协议的一种，具有较好的能耗均衡性，被广泛地应用于无线传感器网络路由中。LEACH(low energy adaptive clustering hierarchy，LEACH)路由协议[6]首次提出了分簇思想，该协议分为簇建立阶段和稳定阶段，在簇建立阶段通过循环方式随机选择簇头节点，将网络能耗平均分配至每个节点，从而在一定程度上提高网络能耗均衡性，延长网络整体生存时间。通过随机方式选择簇头可能导致能量较低的节点作为簇头，造成能耗不均匀。文献[7]将LEACH改进为一种节能多跳路由协议，对LEACH簇的创建、数据传输以及簇的更新等阶段进行了修改，然而该方法构造的多跳路径是未优化的，从而容易导致路由中断。

在网络可靠性方面，文献[8]提出了一种负载均衡和数据收集算法，该算法节约了能耗，提高了数据聚合和转发方面的性能。然而通过多跳的方式进行数据传输，提高了通信成本。文献[9]提出了基于链的路由协议(Chain-chain based routing protocol，CCBRP)，CCBRP集成了传感器信息系统(PEGASIS)的过滤和能量高效收集功能，将整个节点安排到不同的链中。CCBRP提供了一个混合方案，并在两个不同的阶段执行所构建的链。该协议的主要问题是随着网络规模的增大而带来的高能耗和高延迟。因此，由于可扩展性的限制，CCBRP不适合于大规模网络。文献[10]提出了LEACH-MAC协议，改进了LEACH协议随机产生簇头节点导致能耗不均的问题，该方法通过控制簇头数量为一定数值，提高网络生存时间。文献[11]提出了LEACH-ER协议，通过能量和数据可靠性因子选择簇头，该协议通过降低簇头和成员节点之间的簇内部数据包的接收速率，从而提高网络寿命和能源效率。然而该协议并未对路由进行优化，容易导致数据重传和路由中断，可靠性有所欠缺。

在路由数据安全性方面，文献[12]提出的大规模无线传感器网络的可靠且节能的数据收集方法，在热点区域，选择较少的节点来捕获信息，而在非热点区域则选择较多的监控节点。然而，所提出的解决方案忽视了数据安全，在恶劣复杂的环境中，将会给网络带来安全性问题。文献[13]提出了三因素认证方法，为无线传感器网络提供了数据安全保障，提出的方法在节点之间提供了适当的相互认证，但是在认证过程中消耗了不必要的能量，降低了网络的生存期。文献[14-15]使用Shamir加密共享方案设计无线传感器网络数据加密方法，为网络数据提供了安全的传输环境，具有一定的代表性。

针对目前无线传感器网络路由协议存在安全性不高、网络可靠性差等问题，提出了一种安全可靠的WSN路由协议(Shamir-based Secure Reliable Routing，SSCRP)，在簇头的选举中对节点剩余能量、信号强度以及节点到基站的最短路径长度等进行综合考虑，考虑到恶意节点的加入，网络使用Shamir密钥共享算法对数据进行加密，当网络工作一段时间后进行簇首的轮换。该协议能够在保证数据安全性的情况下，提高网络能耗的均衡性以及网络的可靠性。

1 网络能耗模型

1.1 网络相关假设

假设1 网络采用星型网络架构，即网络内所有节点可以直接与基站通信。

假设2 基站由服务器供电，能量充足有足够处理能力。

假设3 无线传感器网络内节点同构，初始能量相同都为E0。

假设4 网络内节点的通信半径为r，在通信半径内节点通信稳定。

1.2 节点能耗模型

节点通信时，节点发送数据和接收收据时都需要消耗能量，其中节点通信能耗模型如图1所示。发送数据能耗和接收数据能耗如式(1)和式(2)所示。

图1 节点通信能耗模型

式(1)、式(2)中:Ee表示数据在发送和接收时每处理1 bit数据时消耗到的能量；Eamp表示功率放大电路的系统；k表示数据包的位数；d表示数据传输距离；dt是距离阈值。

2 路由协议设计

SSCRP协议的主要步骤为:①簇头选择与成簇:根据节点剩余能量、接收信号强度、节点与基站的最短路径长度以及节点的负载率等因素，进行簇头节点的选择，网络内节点全部加入相邻簇头形成簇。②数据加密传输:基站使用Shamir密钥共享算法给网络内所有节点发送密钥，验证节点是否为非法节点。③簇头轮换:利用簇头轮换方法更新簇头，实现网络能耗的均衡性，提高网络数据传输的可靠性。

2.1 簇头选择与成簇

在初始阶段，节点被随机部署于正方形的网络区域内，每个节点都保持静态，且具有唯一的ID。基站向网络区域内的所有节点通过多跳的方式广播其位置，节点接收到数据后通过合并邻居节点的信息更新自身的路由表。接着在网络区域内以分散的方式发布簇头选择机制。由于簇头节点不仅需要处理簇内成员节点的数据，还需要转发其他簇头的数据至下一跳簇头节点，所以与簇内成员节点相比需要更多的剩余能量、更强的接收信号强度等。

因此本文提出的簇头选择机制，通过节点剩余能量(Eres)、接收信号强度指示(Received Signal Strength Indicator，RSSI)、节点到基站的最短路径长度(Dsp)以及节点的负载率(LF)等因子，计算所有节点的竞争值CV，竞争值CV越大表示节点出任簇头的机会越大，就越容易成为簇头。每个节点通过交换控制消息来接收邻居节点信息。节点剩余能量(Eres)是影响网络生存时间最重要的因素，节点的剩余能量越多，表示节点的竞争能量越强，就越容易成为簇头。接收信号强度指示(RSSI)是衡量无线链路质量的一个重要标准，假设节点信标包的接收速率为X，某段时间内，有N个邻居节点向该节点发送信标数据包，节点能够顺利接收数据包且没有发生丢失和重传，则该节点信标数据包的平均接收速率为RSSIth，如式(3)所示，则可将RSSIth作为RSSI的阈值。

当节点的RSSI值小于阈值时，表明链路质量低，丢包率上升。当RSSI值大于RSSIth时，能够提供良好的包接收速率，数据传输就越稳定，此时该节点就越容易出任簇头。当节点至基站的最短路径长度(Dsp)越小时，数据转发的次数就越少，能耗就越低，因此尽量选择最短路径长度短的节点作为簇头。节点的负载率(LF)也是影响数据传递性能的一个重要标准，节点负载率通过节点此时接收的包的字节数(RP)，以及节点的总缓冲大小(TB，以字节为单位)进行衡量，如式(4)所示。

节点的负载率越小表示该节点此时的处理能力就越强，网络越不容易拥塞，该节点出任簇头的概率就越大。

最后，对所有影响因子进行加权，计算出节点的竞争值CV，如式(5)所示。对网络内所有节点的竞争值进行排序，选举出前K个CV值最大的节点作为簇头节点，其中K为网络内的簇头节点数量。

式中:w1、w2、w3、w4分别表示影响因子对应的加权值，且权值满足w1+w2+w3+w4＝1。

当选举出K个簇首节点时，簇首节点向周围邻居节点广播信号帧，当邻居节点接收到状态信息后，都加入至相邻簇头以形成簇，由于邻居节点可能接收到多个簇头发送的状态信息，此时邻居节点将与RSSI值最大的簇头关联形成簇。当完成簇的建立之后，为所有的簇分配一个唯一的簇ID，形成簇集合(Scluster＝{c1，c2，…，ck})，以指定簇边界，所有簇头节点根据时分多址(Time Division Multiple Access，TDMA)发布信道访问方案时间表。从而完成整个网络路由建立。其中具体的路由建立过程如表1所示。

表1 路由建立过程

2.2 簇头选择与成簇

为防止恶意节点入侵网络从而破坏或者窃取网络数据，提出了基于Shamir密钥共享算法的数据加密方法。基站生成密钥S，该密钥使用Shamir的(t，n)密钥共享算法将其传递给n个簇头节点，其中簇头的任意t个子集都能够重建密钥S。Shamir密钥共享算法需要满足下面两个条件:

条件1:任意t个或者大于t个子键的组合(S0，S1，…，St-1)都能够重构密钥S。

条件2:小于t个子集的组合不能重构密钥S。

在Shamir密钥共享算法中，利用t-1次多项式对数据进行加密，其中构造的多项式如式(6)所示，假设将S的值赋值给a0，当通过t个子集求解出多项式的系数集合(a0，a1，…，at-1)时即可实现密钥的重构。

为了实现加密密钥的重构，需要通过拉格朗日插值公式进行计算，如式(7)所示。

基站将密钥Si的每个子键分配给K个簇头，簇头将密钥发送给簇中的成员节点。当成员节点向簇头节点转发网络数据Di时，将密钥Si和数据网络数据Di进行异或操作进行加密，如式(8)所示。

簇头从成员节点接收到加密数据EDi后，将其传输至基站，基站使用解密密钥S对数据进行解密，最终实现网络数据的安全传输，从而防止恶意节点的侵入给网络带来安全性问题。具体的安全数据路由实现步骤如表2所示。

表2 安全数据路由实现过程

2.3 簇头轮换

由于无线传感器网络内，不同区域的簇负载程度不同，负载大的簇头消耗的资源多，容易因能量耗尽而死亡。为了实现能耗的负载均衡提高网络整体的生存期，需要动态地轮换簇内的簇头。当出现以下情况时需要进行簇头轮换:

情况1当簇头接收到网络数据包时，首先判断是否已经接收到相同的数据包，如果是，则丢弃该数据包，以减少网络拥塞和能耗。如果接收到的是一个新的数据包，簇头将会判断自身的剩余能量是否充足，即是否满足Eresi≥Ethreshold(其中Ethreshold是簇头所在的簇的所有节点的平均能耗)，如果不满足则不进行数据包转发，此时在簇内计算所有成员节点的竞争值CV，并将CV值最大的节点作为该簇新的簇头节点。

情况2计算每个簇的拥塞率Cr，如式(9)所示。不断地检查拥塞率Cr的值，当检查到Cr的值不在[0，1]范围内时，表明该簇的簇头已经出现了网络拥塞，此时需要利用2.1中的方法重新进行网络内簇头的选择，实现新一轮簇头的轮换。其中簇头轮换的具体实现如表3所示。

表3 簇头轮换过程

式中:ADR表示数据包之间到的平均延迟率；ARR表示数据包的平均接收效率。

3 仿真实验分析

在i7处理器、8 G内存的PC机中利用NS2仿真平台对本文提出的WSN路由协议进行性能分析。将不同数量的节点随机部署于正方形区域内，其中包含了10个恶意节点，恶意节点通过广播错误的路由数据包，以便被选作数据转发的下一跳。其中仿真参数如表4所示。

表4 仿真参数表

3.1 权重因子影响

为了衡量本文提出的SSCRP协议在不同加权值情况下对网络性能的影响，将100个传感器节点随机部署于100 m×100 m的区域内，网络参数按照表4设置，将不同加权值参数分为三组:组1权值配置为w1＝0.1、w2＝0.5、w3＝0.3、w4＝0.1；组2配置为w1＝0.2、w2＝0.1、w3＝0.1、w4＝0.6；组3配置为w1＝0.5、w2＝0.3、w3＝0.1、w4＝0.1；对这三组配置进行能耗、路由中断次数和数据包传递率分析。结果如图2~图4所示。

图2 簇头节点个数与网络能耗关系

图4 簇头节点个数与数据包投递率关系

从图2~图4可以看出，不同权值情况下，选举的不同簇头对网络的能耗、网络中断次数以及数据包投递率都有相应影响。从图2中可以看出分配给剩余能量(Eres)权重值最大的组3，网络能耗最低。因为在簇头的选举时，能耗所占权值大，因此对能耗考虑的越充分。从图3可以看出组1分配给信号强度(RSSI)的权值最大，路由中断次数最少。因为当节点信号强度较大时，表明此时节点的通信质量高，则此时网络中断次数少。从图4可以看出组2的节点的负载率(LF)占比最大，此时数据包的投递率最高。原因是当对节点的负载率考虑越充分时，此时节点能够转发的数据包能力就越强，则数据包投递率就越高。

图3 簇头节点个数与路由中断次数关系

3.2 端到端时延分析

为了评估本文提出的WSN路由协议性能，本文以下的实验部分将其与CCBRP[9]、LEACH-MAC[10]和LEACH-ER协议[11]进行对比。并将簇头选举时的权值参数设置为相同，即w1＝w2＝w3＝w4＝0.25。

理论上随着节点数量的增多，网络内的流量增大，拥塞情况严重，此时端到端的时延就会增大。实验结果如图5所示。

图5 端到端平均延时

从图5可以看出，随着节点数量的增多，端到端的延时都在不断增大，其中本文提出的SSCRP方法平均延时最低，且随着节点数量的增多网络流量和网络负载迅速上升，SSCRP协议具有更低的端到端延迟。原因是SSCRP协议通过自适应的方式形成簇，并根据簇头的当前性能进行及时轮换，从而减少了路由空洞的出现，降低了数据延迟。

3.3 数据包交付率分析

数据包交付率是评价路由协议性能的重要指标之一，理论上网络处理能力越强，网络数据安全性越高，数据包交付率就越高。其中数据包交付率实验结果如图6所示。

图6 数据包交付率

从图6可以看出随着节点数量的增多，数据包交付率都在降低，原因是随着节点数量的增多，网络流量和网络负载都在急剧上升，因此导致有些数据包出现拥塞，导致数据包丢失，交付率降低。可以看出本文提出的SSCRP交付率最高，且随着节点增多，交付率仍维持在较高水平。原因是SSCRP在簇头选择时充分考虑了多个因素，优先考虑性能较优的节点出任簇头，从而生成更加稳定高效的簇。并且SSCRP采用基于Shamir密钥共享算法的数据加密方法实现了基站和簇头之间通信时数据包的可靠性，减少了路由的中断，最终提高数据交付性能。

3.4 节点平均通信成本分析

节点平均通信成本是衡量WSN路由协议性能的一个标准，节点的平均通信成本越低，则该路由协议性能就越优越。其中节点平均通信成本的实验结果如图7所示。

图7 节点平均通信成本

从图7可以看出随着网络节点密度的增大，四种协议的平均通信能耗都在不断上升，其中本文提出的SSCRP协议的平均通信成本最低，特别在网络负载增大时，节点的平均通信成本仍维持了较低的水平。是因为SSCRP在簇头选举时，对节点的剩余能耗进行充分考虑，当簇的剩余能量不足或者簇的拥塞率大于一定阈值时，进行簇头轮换。SSCRP采用基于Shamir密钥共享算法的数据加密方法保证了数据的安全性和可靠性，从而降低了数据包重发次数，降低通信成本。

3.5 网络生存时间分析

网络生存时间是衡量路由协议优劣的一个重要标准。在同等条件下，网络生存时间越长的网络，表示网络的能耗均衡性就越好，路由协议就越优秀。其中网络生存时间实验结果如图8所示。

从图8可以看出，在相同节点密度下SSCRP路由协议的网络生存时间明显高于CCBRP、LEACHMAC和LEACH-ER协议。因为当簇头节点的剩余能量低于簇内成员节点的平均剩余能量时，SSCRP在该簇内重新计算节点竞争值CV，并指定竞争值最大的节点出任簇头，而不是重新计算整个网络中节点的竞争值，重新轮换所有簇头，因此在一定程度上降低了计算时的能耗，提高了整个网络的生命周期。可以看出LEACH-ER的生命周期最短，虽然LEACH-ER在簇头选举时考虑了节点的剩余能耗和RSSI值，但是并没有考虑到节点与基站的最短路径长度以及网络负载率等因素，因此容易导致数据重传和路由中断，能耗上升，生命周期缩短。

图8 网络生存时间

4 总结

本文基于Shamir密钥共享算法提出了一种安全可靠的WSN路由协议(SSCRP)，与现有的路由协议相比，在端到端时延、数据包交付率以及网络生存时间方面都表现出较好的性能。提出了一种优化簇头的选择过程，采用分布式策略生成簇，并根据簇头剩余能耗和簇的拥塞率及时轮换簇头，使能耗更加均衡。为了防止恶意节点侵入网络，使用基于Shamir密钥共享算法的数据加密方法，保护数据从节点到簇头再到基站这条链路的数据安全。下一步的工作，将SSCRP协议应用到实际场景之中，进行性能验证。