基于最短路径树的分布式功率控制路由算法*

陈友荣，任条娟，刘半藤，葛灵晓

(浙江树人大学信息科技学院，杭州 310015)

无线传感网通常有一个重要目标——延长网络生存时间。由于大部分情况下所有节点的能量有限，不能补充和更换，一旦节点能量耗尽，该节点就会失效，这将影响到网络的运行，甚至可能导致网络的瘫痪，因此延长网络生存时间可以节省重新部署无线传感网的巨大开销［1］。

目前，无线传感网路由的研究已取得一些成果。文献［2－3］用分布式的线性规划公式表示路由问题，采用对偶分解和次梯度方法求解最优路由方案，最大限度提高网络生存时间，但是用最优化方法研究路由方案的算法复杂，很难在实际硬件环境中实现。文献［4］提出LET(Least Energy Tree)算法。它是根据dijkstra算法构建每个节点到Sink节点能耗最小的最短路径树，最终所有节点沿着最短路径树将数据发送给Sink节点。文献［5］在LET算法的基础上提出了“比例权值路由算法”Ratio_w(Ratio Weight Routing Algorithm)与“和权值路由算法”Sum_w(Sum Weight Routing Algorithm)。文献［6］提出多树路由，在数据发送过程中从多个树路径中选择当前合适的路径，最终平衡节点能耗，提高网络生存时间。上述路由算法都假设Sink节点能获得整个网络拓扑信息或者节点能获知与邻居节点的距离，而且节点可根据与邻居节点的距离自动调整发送功率，从而减少链路能耗。如果Sink节点要得到整个网络拓扑信息或者节点要获知与邻居节点的距离，可通过以下两种方法实现。第1种方法是添加额外硬件模块，如配置GPS模块收集每个节点的位置坐标，或者采用超声波、红外等模块测量节点间距离，通过定位方法计算每个节点的位置坐标。……