无线传感器网络中带惩罚因子的路由协议

谭立兴，陈光亭，李溢洁，徐冬冬

(杭州电子科技大学运筹与控制研究所，浙江杭州310018)

0 引言

无线传感器网络是一种基于无线通信技术的、低功耗的和自组织的网络，一般由一个或多个基站和大量部署于监测区域、配有各类传感器的无线网络节点构成。WSN具有十分广阔的应用前景，在军事国防、工农业、生物医疗、环境监测、抢险救灾等许多重要领域都有潜在的实用价值，已经引起了许多国家学术界和工业界的高度重视，被认为是对21世纪产生巨大影响力的技术之一［1］。网络均衡是一个非常重要的问题，如何根据无线传感器网络的自身特点，设计合适的路由协议，有效减少网络能量的消耗和获得高效的、可靠的传输路径，延长节点和网络的寿命，对无线传感器网络的发展具有极其重要的意义。为了提高无线传感器网络的性能，提出了许多路由协议［2-6］，其中包括平面路由协议与分层路由协议，这些协议将各自独立的节点组成一个共同完成某个特定任务的高性能网络结构。本文针对无线传感器网络中局部节点耗能过快问题，以网络均衡的思想解决WSN路由问题，提出一种低能耗的、带惩罚函数的路由协议。协议采用平面路由策略，路径选择过程中既考虑了路径的能耗，也引入了惩罚函数作为路径选择的依据，这样就使得协议在保证总能耗比较少的同时又考虑了数据传输的可靠性。实验表明该算法具有比SPRP等算法具有更好的能量均衡性，从而有效的延长了网络寿命。

1 WSN选路过程的建模及分析

1.1 一般网络路由模型

通常用带权重的连通图Gwsn=(V，E，ω)表示给定的无线传感器网络，其中V是顶点集，E是边集，ω:E|→R+为E中每条边所赋的一个权重值。无线传感器网络的路由模型就是为了寻找WSN中从所需各个传感器节点到基站按某种特定需求的最优路径，如:能量最短路径、距离最短路径等等。

1.2 带惩罚网络路由模型

为了设计更优的无线传感器网络路由协议，定义了一个路由惩罚函数f。用(Gwsn，twsn，α，f)表示无线传感器网络路由模型，其中:

(1)twsn表示无线传感器网络的网络寿命，本文将其定义为从一开始直到第一个传感器节点死亡的这段时间;

(2)Gwsn=(V，E，ω)表示给定的无线传感器网络，其中V是顶点集，E是边集，ω:E|→R+为E中每条边所赋的一个权重值;

(3)α表示惩罚阈值，即重复经过eij∈E的次数大于αn(其中n表示E的总节点数)就要受到惩罚;

(4)本文采用的是线性惩罚，即f=kω(其中k为惩罚系数)。

1.3 无线能量模型

无线传感器的能耗主要包括3个部分:传感器模块、处理器模块和无线通信模块，其中无线通信模块是主要的耗能点，本文采用的无线通信模型是文献6所叙述的自由空间模型，无线通信模块包括无线发送模块、放大模块和无线接收模块，当传输k bit数据时，各个部分的能耗满足下列关系:

式中，ETx(k，d)表示源节点发送k bit数据到距离为d的基站的能耗，ERx(k，d)表示节点接收k bit数据的能耗，Eelec=50nJ/bit为传输电路或接收电路的能耗，εamp=10pJ/bit/m2为传输放大电路的能耗。

2 算法分析与设计

在文献3提出了基于M2WSN的协议SPRP用于节省节点的能量，SPRP主要分为两个阶段:邻居发现和最短路径的构造。邻居发现通过广播HELLO包来得到F节点的邻接矩阵，最短路径的构造则是利用Floyd算法得到各个所需F节点到基站的最优路径。假设SPRP调用Floyd算法的F节点有很多个并且F节点能量有限，则必然出现所有最短路径中存在重复出现次数很高的节点，此现象表示整个WSN具有很差的网络均衡性。所以，不妨以牺牲少部分的总耗费能量来换取WSN具有更好的网络均衡性。本文将给出PSPRP算法的设计细节，本算法的主要思想是:在无线传感器网络中找从源节点到目的节点最小耗费能量路径的同时;也考虑网络的可靠性问题，即数据传输过程中如果仅考虑能耗最少可能会导致一部分节点能量消耗过快而死亡。在本算法中，通过引入惩罚函数的思想，将一部分能量消耗过快节点的能耗转移给能量消耗较少的节点。

PSPRP算法的主要步骤:

(1)给定传感器节点的坐标、初始能量E0，初始化无线传感网络，并建立邻接矩阵;

式中，r0表示传感器的的传输半径，(xi，yi)表示传感器节点i的坐标，(xj，yj)表示传感器节点j的坐标.，dij表示传感器节点i与传感器节点j之间的距离;

(2)利用Floyd算法分别求出所需传感器节点到基站的最短路径，对给定一个无线传感器网络Gwsn=(V，E，ω)，其中，得到一个矩阵序列{εk|k=0，1，…，n}(k 表示中间节点的个数)，其中ε0=(ωij)n×n，εk(i，j)表示节点i到节点j、且满足中间节点皆属于集合{1，2，…，k}的一条最短路径的能耗值，且有;

(3)统计Step 2中所有能量最短路径中每条边被使用的次数num;

(4)判断num是否大于给定的惩罚阈值，如果大于惩罚阈值则边权改变，否则不变;惩罚关系表示如下;

式中，ωij表示边eij的能量权重，α表示惩罚阈值，k为惩罚系数;

(5)更新邻接矩阵并调用Floyd算法，再统计每个节点所耗能量， k)，即每个节点的能耗为最短路径中所有由该节点发出的边的能量和;判断是否有节点死亡，如果不存在Ei〉E0(即不存在节点死亡)，则更新邻接矩阵并返回(2);反之，输出最终的结果。

由于传感器节点的密集性和随机分布性，则存在一小部分节点能耗过快导致过早死亡，这在无线传感网络需要得到精确结果的应用领域是不被允许的，如军事领域等。为了解决上述现象，设计了PSPRP协议。在步骤2中，调用Floyd算法的时间复杂度是o(n2)，在步骤3中，虽然统计所有能量最短路径每条边被重复使用的次数，但是由于传感器集群数目庞大，只从中挑选出能耗过快的少部分节点。

3 仿真验证与分析

为了评价改进后的PSPRP协议的性能，本文对PSPRP算法和SPRP算法进行了仿真实验。在200m×200m的正方形WSN监测区域中，随机部署了200个传感器节点，如图1所示，基站位于(0，0)处，所有节点一再放置就不再移动。惩罚阈值α=20%，惩罚系数k=2，传输半径r0=87m。

如图2所示，横坐标表示的是随机分布的200个传感器节点，纵坐标表示的是各个传感器所耗费的能量值。

图1 200个节点的随机分布图

图2 200个节点的能耗仿真结果示意图

仿真结果显示PSPRP算法比SPRP算法具有更好的网络均衡性，就拿两种算法耗能最多的节点相比，SPRP算法中耗能最多的节点是59(39 672m2)，消耗的总能量为311 803m2。而PSPRP算法中耗能最多的节点是97(27 030m2)，消耗的总能量为320 161m2。通过对比发现PSPRP算法中耗能最多的节点比SPRP算法节约32%，但总耗能只增长0.026%。综上所述，PSPRP算法比SPRP算法具有更好的网络均衡性是以增长小幅度的总耗能为代价。

4 结束语

设计有效的路由协议目的就是要利用节点有限的资源，完成高效的数据传输任务，延长网络的使用寿命，提高节点的能效，并保证一定的灵活性、可靠性和鲁棒性。在PSPRP协议中，采用“分治”的策略，将能量最短路径上的所有边划分为惩罚边和正常边，这样就可以有效的减少能量消耗过快节点的能耗。但是PSPRP算法还有很多待解决的问题，比如算法对网络环境动态变化的适应性问题(节点移动性、通信状态的变化等等)，而且负载均衡只在惩罚区域内部实现，未能在全局范围内考虑，之后将在这些方面对算法进行进一步的优化。

［1］ Li JZ，Gao H.Survey on sensor Network Research［J］.Journal of Computer Research and Development of china，2008，45(1):1-15.

［2］ Heinzelman W，Chandrakasan A，Balakrishman H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEETransWireless Commum，2002，1(4):660-670.

［3］ Duan Zhi-feng，Guo Fan，Deng Ming-xing，et al.Shortest Path Routing Protocol for Multi-layer Mobile Wireless Sensor Net Works［C］.WuHan:Huazhong University of Science and Technology，2009:106-110.

［4］ Intanagonwiwat C，Govindan R，Estrin D，et al.Directed diffiusion for wireless sensor networking［J］.IEEE/ACM Trans On Networking，2003，11(1):2-16.

［5］ 崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展［J］.计算机研究与发展，2005，42(1):163-174.

［6］ Heinzelman W，Chandrakasan A，Balakrishman H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］.Hawaii:Proceedings of the 33rdAnnual Hawaii International Conference on System Sciences，2000:10-19.