不确定环境下无线传感器网络路由算法研究

【作者】 卢俊岭；

【导师】 王小明；

【作者基本信息】 陕西师范大学 ， 计算机软件与理论， 2013， 博士

【摘要】 物联网实现人和物的连接,感知和采集数据的无线传感器网络(Wireless Sensor Networks, WSNs)是其感知事物的核心技术。随着无线传感器网络的普及和研究的深入,基于确定性环境的假设前提,开展资源有限网络路由问题的研究难以满足实际应用的需求。无线传感器网络在部署环境、无线通信、服务质量和网络拓扑等方面同时存在众多不确定性,既有刻画事件发生与否的随机性,也有刻画对事件主观认识的模糊性。在不确定网络环境下研究无线传感器网络的路由问题,需要相应的不确定性理论和优化理论来刻画路由过程中的各种不确定因素,包括干扰模型、传播模型、移动模型和服务质量等,从而为不确定环境下WSN路由算法的研究提供理论基础和保证。为了刻画WSN路由的不确定性,论文基于概率论、模糊集理论、模糊随机理论和优化理论进行路由模型的建模,重点对无线干扰、网络模型、服务质量和路由优化模型的不确定性进行分析和表示,同时设计相应的路由算法和仿真实验开展不确定环境下WSN路由算法的研究。论文的主要工作概括如下：(1)针对干扰条件下无线链路数据传输的随机性特征,综合考虑数据传输的发送节点和接收节点,分别基于信道竞争和物理干扰模型推导出数据成功传输的可能性,提出了干扰条件下数据成功传输概率的发送模型和接收模型,构造了跨层设计的干扰感知路由指标,设计了干扰感知的概率路由(Interference-Aware Cross-layer Probabilistic routing, IACP)算法,分析了该算法的正确性和时空复杂度。基于NS2平台的仿真实验表明,与典型的自组织按需距离矢量路由算法相比,由于考虑干扰的影响,尽管IACP路由算法所找到路径的平均长度略有增加,但采用IACP路由算法的无线传感器网络在包递交率、吞吐量、抖动和较大规模下平均时延等方面具有更好的性能表现。(2)针对无线信号功率随机衰减和干扰条件下无线链路数据传输的随机性特征,基于无线传感器网络概率网络模型和物理干扰模型,推导出干扰条件下数据成功传输的概率干扰模型,构造了综合干扰、路由收敛性和节点剩余能量等因素的路由指标,讨论了路由指标和各种影响因素之间的关系,设计了概率网络模型下的干扰感知路由(Probabilistic Network Model based Interference-aware Routing, PNMIR)算法,分析了该算法的正确性和时空复杂度。基于NS2平台的仿真实验表明,结合典型的随机路点移动模型,针对停留时段和运动速度上界两个模型参数的不同取值,在兼顾单个包能耗和平均时延的同时,干扰感知的PNMIR路由算法比典型的贪婪周边无状态路由算法均具有更高的包递交率,能够更好地满足要求较高可靠性的应用场景。(3)针对无线传感器网络服务质量同时具有模糊性与随机性的双重特征,引入模糊数和模糊概率,在多约束与多路径路由模型的基础上,得到了基于模糊随机规划的多约束与多路径路由模型,统一刻画了服务质量约束的随机和模糊双重不确定性,实现了模糊随机规划路由模型的线性化,设计了基于模糊随机规划的多约束与多路径路由(Fuzzy Random Multi-constrained Multipath routing, FRMCMP)算法,分析了该算法的正确性和时空复杂度。基于NS2平台的仿真实验表明,随着服务质量约束的模糊感知,与仅考虑随机性的多约束与多路径路由算法相比,FRMCMP路由算法在及时包递交率和平均时延两个性能指标上具有更大的表示范围,通过置信水平的改变,能够在不同程度上调节及时包递交率和平均时延,从而更好地满足不同无线传感器网络应用场景的需要。(4)针对无线传感器网络优化目标和约束同时具有模糊性与随机性的情形,基于模糊随机期望值模型及其标准差扩展,结合多目标优化理论,分别给出了不同的模糊随机多目标优化路由模型,讨论了模糊随机变量与模糊随机函数的期望值和标准差的计算方法,利用在基于Pareto排序的遗传算法中嵌入模糊随机模拟的方法,分别构成混合模糊随机遗传路由(Hybrid Fuzzy Random Genetic routing, HFRG)和模糊随机多目标优化路由(Fuzzy Random Multi-Objective Optimization routing, FRMOO)算法进行求解。基于Matlab平台和C语言混合编程的仿真实验表明,上述路由算法一次求解同时得到多条最优路径,具有很好的灵活性和高效率,而且与仅考虑随机性或者模糊性的路由算法相比,所提出的路由算法具有更长的生存周期,能够在更大范围内合理地平衡无线传感器网络的多个性能指标,具有良好的鲁棒性。论文研究在国家自然科学基金“不确定环境下的无线多媒体传感器网络数据传输新机制研究”(编号：60970054)和“移动无线传感网中恶意代码传播的时空动力学理论和方法研究”(编号：61173094)支持下,基于随机不确定性和模糊随机双重不确定性建立了无线传感器网络的多种路由模型,利用不确定性理论同时刻画了路由过程中的随机性和模糊性,设计了不确定环境下的多个WSN路由算法,丰富和完善了WSN路由算法的研究。更多还原

【Abstract】 The internet of things can connect human with things, and wireless sensor networks (WSNs) for sensing and gathering data have been the key technology of sensing things. With the prevalenece of wireless sensor network and the boost of its invertigation, researches on routing problem of wireless sensor network with limited resources, based on the assumptions of certain environment, become diffucult to meet the needs of applications.In wireless sensor networks, many aspects, such as deploy environment, wireless communication, quality of service and network topology, have uncertainties, which include randomness depicting whether an event happens and fuzziness depicting the subjective knowledge of an event. Investigations on routing problem of wireless sensor network in uncertain network environment need the corresponding uncertainty theory and optimization theory, which are used to describe the uncertain factors in routing procedure, such as interference models, propagation models, mobility models and quality of service. Therefore, theorencal bases and guarantees are provided for researching on routing algorithms of wireless sensor network in uncertain environment.In order to depict the uncertainties of routing for wireless sensor network in uncertain environment, the routing problems are modeled based on probability theory, fuzzy set theory, fuzzy random theory and optimization theory, particularly, the uncertainties of wireless interference, signal power fading, quality of service and routing optimization model are analysed and represented. In addition, the corresponding routing algorithms and simulation experiments are designed for further investigations on the routing algorithms of wireless sensor network in uncertain environment. The main works of the thesis are summarized as follows:(1) To describe the random characteristic of wireless data transmission under interference, the likelihoods of successful data transmission are deduced based on channel contention and physical interference model respectively, and the sender and receiver interference models of successful data transmission under interference are proposed by taking into account of both the sender and the receiver in a transmission. Furthermore, the interference-aware cross-layer routing metric is constructed, and the isotonic property of the weight function is proofed. In addition, the IACP (Interference-Aware Cross-layer Probabilistic routing) algorithm is designed, and its correctness and time-space complexity are analyzed. Simulation results based on the NS2platform show that, due to the influence of interference, the proposed IACP routing algorithm can achieve better packet delivery ratio, throughput, jitter and average delay in dense deployment under the different loads at the expense of the comparable average length of paths when comparied with the typical adhoc on-demand distance vector routing algorithm.(2) To describe the random fading of wireless signal power and random characteristic of wireless data transmission under interference, the probability interference model of successful data transmission under interference is deduced based on the probabilistic network model and the physical interference model. Moreover, the routing metric combining interference and routing convergence with residual energies of nodes is constructed, and the relations of the routing metric and the influence factors are discussed. Also, the PNMIR (Probabilistic Network Model based Interference-aware Routing) algorithm is designed, and its correctness and time-space complexity are discussed. Simulation experiments based on the NS2platform show that under the random waypoint mobility model, by simultaneously considering the energy consumption of a packet and average delay, the proposed PNMIR routing algorithm can achieve higher packet delivery ratios in different cases of the pause time and maximum moving speed when compared with the greedy perimeter stateless routing algorithm, which can better meet the needs of the application scenes with higher reliability.(3) To depict the twofold uncertainties, namely, fuzziness and randomness, in quality of service of wireless sensor network, fuzzy number and fuzzy probability are introduced, and the fuzzy random mutli-constrained multipath routing model, which unifiedly describe fuzziness and randomness in the constraints of quality of service, are extended from the mutli-constrained multipath routing model. Furthermore, the linearization of the fuzzy random programming routing model is completed, the FRMCMP (Fuzzy Random Multi-Constrained MultiPath routing) algorithm is designed and its correctness and time-space complexity are analyzed. Simulation results based on the NS2platform show that the proposed algorithm can achieve wider range in terms of on-time packet delivery ratio and average delay, and it can meet the different needs of practical applications for wireless sensor network, because the on-time packet delivery ratio and average delay are flexibly adjusted to different degrees by varing the confidence level.(4) To describe the routing optimization model that has fuzziness and randomness in both objectives and constraints for wireless sensor network, different fuzzy random multi-objective routing models are constructed based on the fuzzy random expected value model and its extension of standard deviation respectively, by combining them with multi-objective optimization theory. The computation methods of expected values and standard deviations of fuzzy random variable and function are discussed, and the HFRG (Hybrid Fuzzy Random Genetic algorithm) and FRMOO (Fuzzy Random Multi-Objective Optimization) routing algorithms are designed for solving problems by embedding fuzzy random simulations into the genetic algorithm based on Pareto sorting. Simulation experiments based on the Matlab platform and the C language show that the above routing algorithms can find multiple optimal paths at a time, possessing flexibility and efficiency. Meahwhile, they can achieve longer network lifetime, reasonable tradeoff in multiple performance metrics and good robustness when compared with the routing algorithms only considering randomness or fuzziness.In this thesis, supported by the National Natural Science Foundation of China entitled "Research on new schemes of data transmission for wireless multimedia sensor networks in uncertain environment"(Grant No.60970054) and "Research on theories and methods of temporal-space dynamics about propogation of malicious code in mobile wirless sensor networks"(Grant No.61173094), several routing models for wireless sensor networks are constructed based on the random uncertainty and fuzzy random uncertainty, the fuzziness and randomness in routing procedure are depicted by adopting the uncertainty theory, and multiple routing algorithms for wireless sensor networks in the uncertain environment are also designed, which enrich and improve the researches on the routing algorithms for wireless sensor networks.更多还原