一种新的无线传感器网络安全路由协议

蒋 华，曾梅梅

(桂林电子科技大学 计算机科学与工程学院，广西 桂林541004)

0 引 言

无线传感器网络是物联网中重要的末梢网之一，伴随着物联网的兴起，使得无线传感器网络对安全、能量的需求被推向了更高的层次，促进了人们对无线传感器网络的发展做进一步深入地研究。

在无线传感器网络中，安全高效的路由协议应该包括如下特性:1)降低配置差错的影响;2)减少网络整体能耗;3)确保只有合法节点参与消息转发;4)防止攻击者注入伪造的路由信息。由于无线传感器网络的种种特性，导致路由协议易于受到虚假路由信息攻击、选择性转发攻击、污水池攻击、女巫攻击、蠕虫洞攻击、Hello 洪泛攻击、假冒应答攻击及关键点攻击等［1，2］。而基于密码体系的传统安全机制只能抵抗外部来源的攻击，其设计思路与实现机制都无法解决开放环境下节点被俘获所带来的内部攻击问题［3～4］。已经有大量的研究工作从各个角度来延长网络生命周期和提高网络安全传输指数［5～6］。

在大规模的无线传感器网络中，根据网络拓扑结构，网络中的路由协议分为平面型和层次型2 种协议，但在节点和Sink 节点之间通常采用多跳形式建立连接。典型的平面路由协议有 Flooding，Gossiping，Spin 路由、定向扩散(directed diffusion)协议、谣传路由、有序分配路由(SAR)和基于位置的 GEAR 路由协议等。其中，Flooding［7］和 Gossiping［8］协议存在信息重叠和盲目使用资源问题，且扩展性差。文献［9］通过发送元数据进行协商来发送数据，但可靠性差，同时Sink 周围的节点能量容易耗尽。无线传感器网络中的节点由于自身资源受限、所处环境恶劣等问题，使得它容易被外界所俘获，成为恶意节点的情况。而目前，现有路由协议的研究主要侧重于如何提高节点能量利用率或网络的可信度［4，10］，本文在平面型网络拓扑结构的前提下，提出一种传感器能量高效的安全路由(EESR)方案，该方案使网络性能得到很大的提高。

1 系统模型

1.1 网络模型

假设n 个传感器节点随机均匀分布在一个正方形区域A 内，传感器节点在部署之后就不再移动;惟一的中继节点部署在区域A 以外的一个固定位置，并且部署后网络无需人为维护;网络拓扑结构在组网后相对稳定，移动性比较小;所有节点都是同构的，具备相同的初始能量和数据融合的功能，且都有一个唯一的标识((ID);节点不需要GPS 装备，也不用通过测量的方法知道其具体位置;无线发射功率是可控，即节点可以根据距离来调整发射功率的大小。

1.2 无线能量模型［11］

无线能量模型，是指发射功率的衰减随着传输距离的增大而呈指数衰减。当发送和接收节点之间的距离在d ＜d0时，采用自由空间模型，发射功率呈d2衰减;否则，采用多路径衰减模型，发射功率呈d4衰减。

1.3 无线传输能量模型［12］

无线传输能量模型如式(1)和式(2)所示

其中，式(1)表示发射k bit 数据损耗的能量，由发射电路损耗和功率放大损耗两部分构成，Eelec为无线通信模块接收或发送单位比特数据电路所消耗能量，εfs，εamp分别为发射放大器在2 种信道模型下传送每比特数据所消耗的能量，d0为某一距离值;式(2)表示接收k bit数据的能量损耗，该值仅由电路损耗引起。同时，假设无线信道对称传输，即从节点 u 传送消息到 v 消耗的能量等于从v 传送同样的消息到 u 所消耗的能量。

1.4 信任模型

为了减少信任值较低的节点成为网络传输路径，并且排除网络中的恶意节点，本文针对文献［13］中提出的可信度评价机制做一定的改进

其中，ET为节点的总能量;VIb为由入侵检测系统列出的恶意节点表，1 为好节点，0 为恶意节点;VIr为主动观测值，由节点对邻居节点进行主动监控来获得的;VSr为间接观测值，通过与其他节点交换信息获得的经验值;f1，f2，f3可以根据网络具体要求来设不同的值，假设:f1+f2+f3=1，并进行归一化。

2 算法思想

本文在不考虑空间差异的情况下，将无线传感器网络的节点抽象成图的顶点，网络节点之间的通信关系抽象成图中顶点与顶点之间的连边，那么，无线传感器网络可表示为图G=(V，E)，其中，V 表示传感器网络中节点的集合，E表示网络中节点与节点之间的通信关系。本文提出的方案将数据包在节点间传输所需的能量大小和可信任度值作为边的权值，运用Prim 算法和Kruskal 算法来解决Gossiping算法存在的问题。

2.1 改进后的Prim 算法和Kruskal 算法

Prim 算法和Kruskal 算法是生成最小生成树的经典算法，其中，Prim 算法适用于稀疏图，Kruskal 算法适用于稠密图。本文采用最小生成树的思想来构造出无线传感器网络中的最优路由路径，针对文献［14］的最小生成树算法改进如下:

假设V 为图中顶点的集合，E 为图中边的集合，RE 为最优路由路径中的边的集合，则改进后的Prim 和Kruskal算法通过以下步骤可以得到最优路由路径:

1)改进后的Prim 算法的基本步骤

a.初始化:U ={u0}，RE ={}，其中，u0表示为中继节点;此步骤设立一个只有节点u0的节点集U 和一个空的边集RE 作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断地发生变化，直到得到最小生成树为止;

b.如果V－U={}，则输出最优路由路径R，并结束算法;

c.在所有两栖边中找一条权最小的边(u，v)(若候选两栖边中的最小边不止一条，可任选一条;如果(u，v)=0 值时，把节点v 移出V－U 集合，继续下一步的比较)，将边(u，v)加入到边集RE 中，并将顶点v 并入集合U 中;

d.由于新顶点加入，U 的状态发生变化，需要对U 与V－U 之间的两栖边进行调整;

e.转步骤(2)。

2)改进后的Kruskal 算法的基本步骤

a.初始化:RV={v0，v1，……，vn－1}，RE ={}表示路由;其中，RV 表示一个只含有n 顶点，而边集为空的子图。

b.如果E={}，则输出最优路由路径R，并结束算法;

c.在有序的E(G)边表序列中，从当前位置向后寻找满足此条件权值最小的边(u，v):使得u 在一个连通分量上，v在另一个连图分量上，即(u，v)是满足此条件权值最小的边，将其加入到RE 中，合并u 与v 所在2 个连通分量为一个连通分量，更新E 集合;如果E{(u，v)=0}，则移出边(u，v)。

d.转步骤(2)。

2.2 最优路由路径

本算法分为构建最优路由路径和稳定工作阶段2 个部分组成。每一轮通过在中继节点设置一个时间戳，来对网络最优路由路径进行实时更新。为减少频繁构建最优路由路径产生的能量损耗，所以，稳定工作阶段的时间要足够长。

1)无线传感器网络是以数据为中心的路由机制，它有2 种方法用于信息分发:Sink 节点广播消息;传感器节点广播所获取的消息，等待Sink 节点的查询消息，所以，本文采用由网络中任一节点广播发送用于发现邻居节点请求报文，请求报文信息中携带发送节点的节点信息(ID)和节点对发送节点的E 值(顺序标注)。

2)随着请求报文在网络中的传播，根据无线传感器的特性，最后请求报文信息都会汇聚到Sink 节点，通过请求报文中信息，Sink 节点能够获悉到整个网络的拓扑结构和边权值。

3)中继节点在收到广播路径上的信息后，构造成一个N×N 的矩阵，因为无向图是对称阵，为了减少中继节点的存储，采用了稀疏三元组来存储。

4)在中继节点通过采用改进后的 Prim 算法或者Kruskal 算法实现生成一个最优路由路径。

5)Sink 节点根据最优路径发出查询信息时，然后由感知数据沿查询消息的反向路径向Sink 节点传送，父节点利用数据融合对数据进行处理，来减少数据通信量，如图1、图2所示。

图1 算法思想示意图(无恶意节点情况)Fig 1 Diagram of the algorithm idea(withouth malicious node)

3 模拟与分析

本文在NS2 环境下采用C + + 语言编码实现来仿真的。传感器网络模型的主要参数如下:100 个节点平均分布在100 m×100 m 地域范围A 内，Sink 节点在传感器区域A外任意位置，每个节点的初始能量ET=0.5 J，中继节点采用改进后的Prim 算法进行生成最优路由路径。为了测试该算法的性能，将其与Gossiping 进行比较。图3 为初始能量相同时不同协议的网络生命周期。从图中可以看到:此算法比Gossiping 的生命周期提高了将近7 倍(以最后一个节点死亡为标准)。图4 为无线传感器网络中节点丢包率随恶意节点的变化情况。为了简化实验，本实验通过人为的设置恶意结点，通过图4 可以看出:在不同恶意节点数目，相比Gossiping 协议，本文方法的网络丢包率普遍降低了，丢包率平均降低了大约22%。

图3 初始能量相同时不同协议的网络生命周期Fig 3 The network life cycle of different protocols with the same initial energy

图4 无线传感器网络中节点丢包率随恶意节点的变化情况Fig 4 Loss packet rate of WSNs node changes with variation of malicious nodes

4 结束语

本文提出了一种EESR 协议，通过传感器中的任一节点进行广播请求报文，对路径信息进行标识，Sink 节点根据路径信息，获取到网络拓扑结构的全部信息，根据改进后的Prim 或者Kruskal 算法得出一个最优路由路径，最后由Sink节点发出查询信息，感知数据沿查询消息的反向路径向Sink 节点传送。该算法仅适用于平面型的网络拓扑情况下。

［1］ Kifayat K，Merabti M，Shi Q.Security in wireless sensor networks［Z］.Handbook of Information and Communication Security，Berlin:Springer，2010:513 － 552.

［2］ Sen Jaydip.A survey on wireless sensor network security［J］.International Journal of Communication Networks and Information Security(IJCNIS)，2009，2:55 － 78.

［3］ Boukerch A，Xu L，El－khatib K.Trust－based security for wireless Ad Hoc and sensor networks［J］.Computer Communications，2007，30:2413 － 2427.

［4］ 吴银锋，周 翔，冯仁剑，等.基于节点信任值的无线传感器网络安全路由［J］.仪器仪表学报，2012(1):221 －227.

［5］ Kan Baoqiang，Cai Li，Zhu Hongsong，et al.Accurate energy model for WSNs node and its optimal design［J］.Journal of Systems Engineering and Electronics，2008(3):427 －433.

［6］ 胡向东，魏琴芳，唐 慧.物联网中数据融合的信誉度模型与仿真［J］.仪器仪表学报，2010，31(11 ):2636 －2640.

［7］ Hedetniemi S，Liestman A.A survey of Gossiping and broadcasting in communtication networks［J］.Networks，1998，18(4):319 －349.

［8］ Sinha K，Ghose S，Srimani P K.Fast deterministic broadcast and gossiping algorithms for mobile［J］.Journal of Parallel and Distributed Compputing，2008，68，922 － ，938.

［9］ Kulik J，Heinzelman Wendi ，Balakrishnan H.Negotiation－based protocols for disseminating information in wireless sensor networks［J］.Wireless Networks，2002，8:169 － 185.

［10］ 李训光，颜 听，李腊元.一种基于可视角度能量高效的路由算法［J］.微计算机信息，2009，25(3):216 －314.

［11］ Rappaport T.Wireless communications:Principles and practice［M］.New Jersey:Prentice Hall Inc，1996.

［12］ Heinzelman W R，Chandrakasan A，Bala Krishnan H.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660 －670.

［13］ 章 静，许 力，徐道炜.自组网中基于可信度评价的安全分簇策略［J］.计算机应用，2007，10(27):2426 －2429.

［14］ Levin M S H，Zamkovoy A.A multicriteria steiner tree with the cost of Steiner vertices［J］.Jouranl of Communications Technology and Electronics，2011，56(12):1527 － 1542.