有向传感网络中移动目标栅栏覆盖算法.pdf

2013年10月 北 京 邮 电 大 学 学 报 Oct.2013 第36卷 第5期 Journal of Beijing University of Posts and Telecommunications Vol.36 No.5 摇 摇 文章编号:1007鄄5321(2013)05鄄0006鄄04 DOI:10.13190/ j.jbupt.2013.05.002 有向传感网络中移动目标栅栏覆盖算法 1,2 3 2 陶摇 丹 ,摇 毛续飞 ,摇 吴摇 昊 (1.北京交通大学 电子信息工程学院,北京 100044;2.北京交通大学 轨道交通控制与安全国家重点实验室,北京 100044; 3.清华大学 软件学院,北京 100084) 摘要:通过调整有向传感节点的传感方向,实现网络强栅栏路径的构建. 定义交点集和关联节点集以刻画区域边 界以及相邻节点间位置关系,将问题从二维连续空间映射到二维离散空间;其次,构建全局覆盖图对问题进行建 模,采用图论方法快速判定已知网络布局能否构成强栅栏覆盖.若存在,则选取满足最少节点数目的栅栏路径. 仿 真结果对算法的性能进行了有效验证. 关摇 键摇 词:有向传感网络;栅栏覆盖;关联交点;全局覆盖图 中图分类号:TN915郾03摇 摇 摇 摇 文献标志码:A Barrier Coverage Algorithm for Moving Target in Directional Sensor Networks 1,2 3 2 TAO Dan ,摇 MAO Xu鄄fei ,摇 WU Hao (1.School of Electronic and Information Engineering,BeijingJiaotong University,Beijing 100044,China; 2. State Key Laboratory of Rail Traffic Control and Safety,BeijingJiaotong University,Beijing 100044,China; 3. School of Software,Tsinghua University,Beijing 100084,China) Abstract:Strong barrier path construction for directional sensor networks was focused on by optimizing the sensing orientations of directional sensors. The intersection point set and associated intersection point set were defined to describe the relationshipsbetween directional sensors and region boundaries. The so鄄 lution space from continuousdomainwasreduced. Graph theory wasutilized to construct a global barrier graph tomodelthependingproblem,whetherthedirectionalsensors爷sensingor