基于动态规划的无线传感器网络的路由算法  

Routing Algorithms of the Wireless Sensor Network Based on Dynamic Programming

作　　者：杨文国[1,2] 郭田德[3] 赵彤[3] 

机构地区：[1]中国科学院研究生院工程教育学院 [2]中国科学院科技政策与管理科学研究所北京100085 [3]中国科学院研究生院数学科学学院

出　　处：《计算机研究与发展》2007年第5期890-897,共8页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2002AA103061);中国科学院研究生院院长基金项目(YZJJ200503);中国科学院研究生院科研启动基金项目(055101A)~~

摘　　要：路由问题是无线传感器网络中的核心问题之一,其数据传送的多跳特点使得非常适合用动态规划的原理来设计传感器网络的路由算法.基于动态规划,通过节点跳数生成算法为传感器网络中的每个节点赋一个表示到Sink点跳数的节点跳数值,并分析了传感器网络的拓扑结构特点,然后给出了无线传感器网络中寻找从源到汇满足不同设计目标的最小跳数(MinH)、最小跳数最大剩余能量(MinHMaxRE)和最小跳数最小费用(MinHMinC)3种路由算法.探讨了最小跳数最小费用路由与最小费用路由之间的关系,并给出了判断最小跳数最小费用路径就是最小费用路径的一个充要条件.算法的能量消耗分析表明,所给路由算法能实现大幅度的能量节省.Routing problem is one of the most important issues to the wireless sensor network. In sensor network, data is transmitted from source to sink node in a multi-hop mode, so dynamic programming principle lends itself well to design routing algorithms of sensor network. Based on dynamic programming, a hop value of each node that indicates the hop number needed to communicate with the sink is generated by a node hop number generation algorithm. As the topology of the sensor network is concerned, the difference between the hop values of each node and its neighbor is no more than 2. Then three algorithms, that is minimal hop routing, minimal hop with maximal residual energy routing and minimal hop with minimal cost routing algorithms, are presented in this paper, which can pick up the paths that meet different design target between the sink and the source node in wireless sensor network effectively. The relationship between minimal hop with minimal cost routing and minimal cost routing is studied. A necessary and sufficient condition that minimal hop with minimal cost routing is also minimal cost routing are given. Energy consumption analysis shows that the routing algorithms proposed can be energy saving to a great degree.

关 键 词：无线传感器网络 路由 动态规划 算法 跳数值 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]