基于多目标规划的WSN矩阵乘路由算法
彭利民
【摘 要】摘要：针对无线传感器网络路由中的能量消耗问题，综合考虑节点的能量水平和节点间传送数据的能耗，建立多目标规划的路由模型，并利用矩阵和向量的乘法运算表示无线传感器网络中的路由问题.应用基于优化满意度的评价方法，将多目标路由问题转换为单目标优化问题，并提出一个适合无线传感器网络的矩阵乘路由算法.仿真结果表明，该算法能合理地利用有限的能量资源，较大地延长网络寿命并降低节点的平均能耗. 【期刊名称】兰州理工大学学报 【年(卷),期】2011(037)003 【总页数】5
【关键词】无线传感器网络；动态规划；矩阵；理想点；能量
无线传感器网络通常运行在人无法接近的恶劣甚至危险的远程环境中，大多采用电池供电，电源能量有限且能源无法补充或更换，因此设计有效的策略延长网络生存周期已成为传感器网络的核心问题［1］.无线传感器网络是一个数据采集网络，所有探测节点都需要将感知的数据汇集到Sink节点，而受发射功率限制，节点的覆盖范围有限，所以需要中间节点的转发.由于绝大部分流量由各个传感器节点流向Sink节点，网络流量分布极不均匀，越靠近Sink节点的节点负载越重，相应的能耗就越大，寿命越短，容易出现个别关键节点因能量耗尽而失效，造成网络分割、连通性无法保持而影响正常工作，直接导致网络生存周期的缩短.因此，在设计路由算法的时候，不仅要考虑减少节点的能耗，还要从整个网络系统的角度，根据具体的应用背景，考虑网络能量的均衡使用，
实现延长整个无线传感器网络生存周期的目标.
1 相关工作
怎样高效地利用无线传感器网络中有限的能量，延长网络的生存周期，已成为无线传感器网络领域中一个重要的研究课题［1］.假定各节点可以自适应调节发射功率的基础上，文献［2］利用网络流模型，基于线性规划方法，提出一个最大化网络生存周期的路由算法；文献［3］通过建立网络生存周期的理论模型，利用集中式迭代算法，提出一个传感器网络能量Pareto优化方案；文献［4］提出根据网络中各节点能耗情况，选择合适的节点发送业务数据，均衡传感器网络的能量消耗，从而延长整个网络的生存时间；文献［5］首先利用剪枝策略，裁掉网络中节点能量水平低于某个阈值的边，然后根据节点剩余能量水平设置不同的权重，再利用Dijkstra算法进行路由求解.
在无线传感器网络中，由于发送单位数据所消耗的能量与发送距离的幂次方满足某种线性关系［6］，所以发送数据的能量消耗通常不满足所谓的“三角不等式”，即从vi经v k发送数据传到v j所消耗的总能量不一定大于从v i直接发送数据到v j所消耗的能量，也就是说增加路由跳数，亦有可能降低发送数据的能耗，因此，文献［6］基于动态规划思想提出的最小跳步路由算法不一定是最小能耗路由；另一方面，由于能量消耗“三角不等性”的不确定性，使得路由事先无法预测，因此，无线传感器网络能量优化路由是一个典型的不定期动态规划问题［7］.
本文根据不定期动态规划的思想，提出一个多目标规划的路由方案，达到既减少路由的能量消耗，又使网络中各节点能量均衡分布，从而延长整个网络的生存周期.
2 问题描述
在本文研究中，假定网络节点分为Sink节点（即数据汇聚节点）和普通传感器节点（简称为普通节点）两种.Sink节点及其他普通节点的位置都是固定的，且Sink节点保存整个网络的拓扑结构信息和所有节点的能量信息.Sink节点定期地进行数据收集，普通节点通过单跳或多跳的方式把数据传送给Sink节点.每个普通节点能量有限，而Sink节点能量不受限制，每个普通节点可以调节信号发射功率，以减少不必要的传输能量消耗. 2.1 符号和公式
本文采用文献［8］给出的无线传感器节点工作能耗模型，为了研究方便，和文献［8］一样只考虑各节点用于发送与接收数据的能耗，其他能耗（如计算过程所消耗的能量等）忽略不计，则将一个n－bit的信息传送到距离为d的节点，射频电路的发送能耗和接收能耗分别为 2.2 多目标规划能耗优化模型
为了求解具有最小能耗和能量均衡（选择最大的剩余能量水平的节点作为路由节点）的路由优化解，建立基于多目标规划的能耗优化模型. 优化目标：
3 多目标规划路由模型
无线传感器网络的路由优化问题就是寻找从探测点S到Sink节点R的最优路径.由于动态规划是把一个待求解问题分解成多个子问题，先求解子问题，然后从这些子问题的解得到原问题的最优解，因此，它非常适合用来解决无线传感器网络的路由优化问题.为了便于将无线传感器网络的路由问题转化为动态规划问题，参考文献［10］最短路径问题的动态规划求解方法，建立一个如图1所
基于多目标规划的WSN矩阵乘路由算法
