无线传感器网络RaSMaLai算法的改进

Improvement on RaSMaLai in wireless sensor networks

针对RaSMaLai算法有可能进入无效循环和无效等待状态的问题,对RaSMaLai进行了两点改进并提出了一种新的随机转换算法NRaSMaLai:改进一在算法初始化过程中遍历树中节点进行初始化检查,防止树进入无效等待状态;改进二在更新树操作过程中对树中最大负载节点及其所有子孙节点时进行状态检测,防止树进入无效循环状态。NRaSMaLai通过增大最小负载节点及其子孙节点的负载使树平衡。仿真实验表明,使用改进一、二的算法能使树达到平衡状态或更接近预设的平衡状态。当sink节点位于区域中心时,NRaSMaLai使树平衡时所需的迭代步数减小为原来的1/5并很少出现振荡,对使数据收集树快速收敛并延长网络寿命具有重要意义。

Two improvement methods were presented to avoid ineffective circulation and invalid waiting state problems when running algorithm Randomized Switching for Maximizing Lifetime （RaSMaLai） and then a new random switching algorithm New Randomized Switching for Maximizing Lifetime （NRaSMaLai） was put forward： the first improvement was to conduct the initialized inspection in the process of traversing tree nodes in order to prevent the tree from entering into invalid waiting state; the second improvement was to do the state inspection for the maximum load node and all its descendant nodes in the operation process of updating the tree to avoid ineffective circulation. The tree balance was achieved by increasing the load of the minimum node and its descendant nodes with NRaSMaLai. The simulation experiment shows that these two methods can make the tree achieve the balance state or at least get closer to the presupposed state. When the sink node was located in the regional center, the iterative steps which make the tree balanced can be reduced to 1/5 of the original by NRaSMaLai and also it appears little oscillation. This is significant for the data collection tree＇s rapid convergence and the extension of the network＇s lifetime.