【作者】 张文铸；

【导师】 山秀明；

【作者基本信息】 清华大学 ， 信息与通信工程， 2010， 博士

【摘要】 随着无线传感网络应用研究不断深入，涌现出间歇连通、容迟、容错等新概念，为相关系统分析和设计带来新的挑战。在拓扑控制领域，网络动态覆盖问题和能量效率问题不断凸显，引起学术界和工业界的普遍关注。本文分别针对这两方面问题展开研究，主要工作和创新点包括以下四方面。首先，提出移动传感网络区域覆盖的统计特征，包括首达时间、累积覆盖面积、位置覆盖度和动态覆盖面积等。利用Jackson排队网络对区域动态覆盖问题进行建模，证明了区域覆盖问题在统计意义上等价于排队问题。结合北京市出租车真实运营数据和多种典型移动场景进行仿真，验证了上述理论结果可以辅助分析大规模移动传感网络的基本覆盖能力。其次，提出基于二维元胞自动机的能量调度策略，利用传感网络容迟特征构造间歇连通图。通过“生命游戏”模拟无线传感网络的能量调度过程，从元胞空间上的动力学层次研究节点状态更新问题，提出将元胞空间拓扑演化分为“振荡”、“衰减”、“稳定”三种模式，指出在稳定模式下网络拓扑连通性、覆盖性和生存时间存在折中关系。再次，提出基于局部感知的拓扑控制算法(LIc0)。相比其他方法，LIc0算法充分利用了网络容迟特性，在每个特定时刻网络可能不连通，但在较长时间尺度上可实现端到端可达性。仿真表明，采用s2803规则的LIc0算法下网络生存时间可达LEAcH算法的7倍，代价是牺牲15％左右的动态覆盖面积，网络平均端到端距离增加，并出现间歇连通的情况。最后，提出基于指数退避机制的异步LIc0算法(A—LIc0)，针对大规模传感网络中难以实现全网时间同步的情形，对节点状态更新时机进行了改进。仿真表明，随着平均退避时间的增加，网络寿命增长，代价是动态覆盖能力和网络连通性变差。A—LIc0无需时间同步，更适合一般无线传感网络直用。本论文的理论分忻和原理模型可供进一步研究参考，理论结果和算法设计可以指导实际的无线传感网络工程。更多还原

【Abstract】 Emerging new applications of Wireless Sensor Networks(WSNs) have introducednew features, such as intermittently connectivity, delay tolerance and error-tolerance,which incur new challenges in analysis and development of WSNs. Regarding thetopology control problem, dynamic coverage and energy e?ciency are two criticalfactors that attract both academic and industrial interests. The contributions of thisthesis in this area are listed below.First, theorems are proposed and proved to formulate statistic characters of areacoverage in mobile WSNs, including ?rst hit time, coverage degree distribution, dy-namic and accumulated coverage ratio, et al. Area coverage problem of mobile WSNsis modeled as a Jackson queueing network, and it is proved that the area coverageproblem is equivalent to a queueing problem in terms of statistical problem. By jointsimulations with a variety of mobile models and the real Beijing taxi traces, we showedthat the theoretical results could be used in analyzing large scale mobile WSNs.Second, a Cellular Automata(CA) based energy scheduling mechanism is pro-posed, utilizing delay tolerant features to build intermittently connected graph. Theenergy scheduling is modeled as”game of life”, facilitating the study of sensor statetransition from collective dynamic system viewpoint. It is found that the spacial evolu-tion of CA topology can be classi?ed into several patterns, including oscillation, atten-uation and stabilization. Moreover, the tradeo? relations among connectivity, coverageand system lifetime under the stable mode is revealed.Third, a new topology control algorithm for WSNs, namely LICO(LocalInformation-based Cognition and Operation) is proposed. LICO dose not require con-nectivity of network graph, and sensors can made state transition merely according toone hop interactions. Simulations showed that LICO enjoys much longer network life-time, which is about 7 times of that of LEACH under rule S2B03, in sacri?cing thedynamic coverage ratio by 15%, and the network’s intermittent loss of connectivity. Finally, the asynchronized version of LICO, namely A-LICO is proposed, whichis based on exponential back-o?. Large scale WSNs’lack of synchronization restraintsthe applications and performance of LICO. A-LICO conquer the problem and enjoyslonger lifetime. Simulation shows A-LICO is ?ne turnable in that the coverage andconnectivity quality decreases as the the average back-o? time rises. Therefore A-LICO is more suitable to general large scale WSNs.The proposed theoretical results, prototype and algorithms can be applied to prac-tical WSN applications.更多还原