摘要
无线传感器网络(Wireless Sensor Networks, WSN)正在得到越来越多的关注和研究,其应用也在逐渐增多。在大规模应用中,均匀部署的WSN拓扑概貌主要由部署区域的几何形状决定。由于按事先规划进行部署的方案基本不予考虑,路由等问题必须在随机部署完成后进行自组织。为了能从大局上优化整体性能,必须首先对WSN的整体概况有所了解,其中拓扑瓶颈和边界是最重要的整体信息。
本文通过对比发现,均匀部署的WSN的节点分布情况和组成物质的分子分布情况在微观上具有一定的相似性。微观特征相似的累积很有可能导致宏观特征相似。
为此,本文提出了通过模拟物理过程寻找WSN拓扑边界和瓶颈的思想。首先寻找到了两种物理过程,能够使处在物体几何边界和瓶颈位置的分子群表现出特点。本文发现在封闭有边界的连续空间中对物体进行一定的刺激,通过观察热传导过程中某一时刻的温度场,汇聚到温度梯度为零但非局部极高温点的温度梯度线,可以确定为连续空间的瓶颈；通过观察物质扩散过程中某一时刻的浓度分布,等浓度线的中断处可以确定为连续空间的边界。
为了辨识WSN的拓扑边界,本文提出了一种仅依赖节点间相邻关系的分布式算法。算法首先在WSN中模拟物质扩散过程,建立虚拟的物质浓度分布,然后通过比较WSN各个节点的虚拟物质浓度值,在WSN中建立起近似等浓度线,再通过判断近似等浓度线的中断点,最终辨识出WSN的边界节点。该算法的结果为下一步确定WSN瓶颈提供了必要的前提条件。
为了识别WSN的拓扑瓶颈,在WSN拓扑边界已经确定的前提下,本文提出了一种仅依赖节点间相邻关系的分布式算法。首先在WSN中模拟热传导过程,建立虚拟的温度场,然后通过各节点在邻节点中选择虚拟温度值最高的作为父节点的步骤,在WSN中形成若干拓扑树,最后各节点通过判断其邻节点中是否有属于不同拓扑树节点,最终识别出WSN的瓶颈节点。
本文所提出的算法,思想清晰,易于理解；算法前提简单,有广泛的应用的潜力。算法的输出结果,反映了WSN拓扑结构和WSN部署区域的全局概貌,能对其他WSN优化设计提供有用的信息。
Wireless Sensor Networks (WSN) is becoming increasingly promising in practice, which arouses the global interest and research about it. The underlying geometric feature of the deployment field fundamentally affects the overall topology of the WSN in large scale applications. As the pre-deployment design and optimization are usually unpractical in random deployment scenarios, the global optimum of the WSN's performance is achievable only if the topology dependent self-organizing process acquires the overview of the WSN, in which the bottleneck and the boundary are the most important.
The distribution states are quite similar between the microscopic view over molecules and the uniformly random distributed WSN nodes. The similar microscopic features could very likely lead to a similar macroscopic characteristic.
An idea is proposed that the boundary and the bottleneck of WSN could be recognized by simulating physical processes. Two phenomena are investigated first, as some features could distinguish the molecules at the bottleneck or the boundary and molecules at other positions. By observing the temperature field in heat conduction process after certain stimulation, the bottlenecks show up at the gradient lines that end on the non-extremal points where the gradient equal to 0. By observing a certain mass diffusion process, the boundaries could be identified at the points where the isoconcentration surfaces break.
A distributed algorithm, which only requires the information about the adjacent relation, is proposed for detecting the boundary nodes of the WSN. After simulating the mass diffusion process in WSN, the virtual concentration field sets up and could be investigated. Then the topological boundaries of the WSN are recognized by identifying the break points of the virtual isoconcentration lines. The output of the algorithm also provides the vital information for recognizing the bottleneck.
On the basis of boundary detection, a distributed algorithm, which only requires the neighboring information, is proposed for recognizing the nodes on bottleneck section of the WSN. After simulating the heat conduction process in WSN, a virtual temperature field sets up. When every node selects the hottest node in neighborhood as parent, some topological trees appear in the WSN. The topological bottleneck could be recognized by identifying the nodes in whose neighborhood there are nodes belonging to different trees.
The idea of the proposed algorithms is clear and easy to understand. The assumption of the algorithms is rather weak, which suggests a potential of wide range applications. The output of the algorithms provides the overview of the WSN topology and the shape of the field, which could be very valuable for other algorithms dedicated to optimize the overall performance of WSN.
引文
[1]Borriello G, Want R. Embedded Computation Meets the World Wide Web [J]. Communications of the ACM,2000,43(5):59-66.
[2]Weiser M, Gold R, Brown J S. The Origins of Ubiquitous Computing Research at Parc in the Late 1980s [J]. IBM Systems Journal,1999,38(4):693-696.
[3]Weiser M, Janssen B, Chandy M, Fuchs A, Mulchandani D. Virtual Roundtable: Ubiquitous Computing [J]. IEEE Internet Computing,1998,2(2):96-96.
[4]Weiser M. The Future of Ubiquitous Computing on Campus [J]. Communications of the ACM,1998,41(1):41-42.
[5]Weiser M. Some Computer-Science Issues in Ubiquitous Computing [J]. Communications of the ACM,1993,36(7):75-84.
[6]Weiser M. The Computer for the 21st-Century [M], in Human-Computer Interaction, M.B. Ronald, et al., Editors,1995, Morgan Kaufmann Publishers Inc.:933-940.
[7]Weiser M. Ubiquitous Computing [J]. Computer,1993,26(10):71-72.
[8]Srivastava M, Muntz R, Potkonjak M. Smart Kindergarten:Sensor-Based Wireless Networks for Smart Developmental Problem-Solving Environments [C]. Proceedings of the 7th annual international conference on Mobile computing and networking,2001:132-138.
[9]Cerpa A, Elson J, Estrin D, Girod L, Hamilton M, Zhao J. Habitat Monitoring: Application Driver for Wireless Communications Technology [J]. Computer Communication Review,2001,31(2):20-41.
[10]Rabaey J M, Ammer M J, da Silva J L, Patel D, Roundy S. Picoradio Supports Ad Hoc Ultra-Low Power Wireless Networking [J]. Computer,2000,33(7): 42-48.
[11]Solymar L. Getting the Message:A History of Communications [M]. Oxford Univ. Press:Oxford,1999.
[12]Odlyzko A. Internet Pricing and the History of Communications [J]. Computer Networks,2001,36:493-517.
[13]Akyildiz I F, Su W, Sankarasubramaniam Y, Cayirci E. Wireless Sensor Networks:A Survey [J]. Computer Networks,2002,38(4):393-422.
[14]Asada G, Dong M, Lin T S, Newberg F, Pottie G, Kaiser W J, Marcy H O. Wireless Integrated Network Sensors:Low Power Systems on a Chip [C]. Proceedings of the 24th European Solid-State Circuits Conference (ESSCIRC '98),1998:9-16.
[15]Bonnet P, Gehrke J, Seshadri P. Querying the Physical World [J]. IEEE Personal Communications,2000,7(5):10-15.
[16]Burrell J, Tim B, Beckwith R. Vineyard Computing:Sensor Networks in Agricultural Production [J]. IEEE Pervasive Computing,2004,3(1):38-45.
[17]Chandrakasan A, Min R, Bhardwaj M, Cho S, Wang A. Power Aware Wireless Microsensor Systems [C].28th European Solid-State Circuits Conference (ESSCIRC),2002:47-54.
[18]Estrin D, Girod L, Pottie G, Srivastava M. Instrumenting the World with Wireless Sensor Networks [C].2001 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'01),2001:2033-2036.
[19]Estrin D, Govindan R, Heidemann J, Kumar S. Next Century Challenges: Scalable Coordination in Sensor Networks [C]. Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking,1999: 263-270.
[20]Hill J L, Culler D E. Mica:A Wireless Platform for Deeply Embedded Networks [J]. IEEE Micro,2002,22(6):12-24.
[21]Huang G T. Casting the Wireless Sensor Net [J]. Technology Review,2003, 106(6):50-56.
[22]Mainwaring A, Culler D, Polastre J, Szewczyk R, Anderson J. Wireless Sensor Networks for Habitat Monitoring [C]. Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications,2002:88-97.
[23]Pottie G J, Kaiser W J. Wireless Integrated Network Sensors [J]. Communications of the ACM,2000,43(5):51-58.
[24]Steere D C, Baptista A, McNamee D, Pu C, Walpole J. Research Challenges in Environmental Observation and Forecasting Systems [C]. Proceedings of the 6th annual international conference on Mobile computing and networking,2000: 292-299.
[25]Szewczyk R, Osterweil E, Polastre J, Hamilton M, Mainwaring A, Estrin D. Habitat Monitoring with Sensor Networks [J]. Communications of the ACM, 2004,47(6):34-40.
[26]Zhao F, Shin J, Reich J. Information-Driven Dynamic Sensor Collaboration [J]. IEEE Signal Processing Magazine,2002,19(2):61-72.
[27]Bhardwaj M, Garnett T, Chandrakasan A P. Upper Bounds on the Lifetime of Sensor Networks [C]. IEEE International Conference on Communications, ICC, 2001:785-790.
[28]Li D, Liu W, Zhao Z, Cui L. Demonstration of a WSN Application in Relic Protection and an Optimized System Deployment Tool [C]. Proceedings of the 7th international conference on Information processing in sensor networks,2008: 541-542.
[29]Jen-Chu L, Kuo-Yu C, Cai-Fang Y. A Highly Flexible System for Smart Home Sensor Networks [C].4th International Conference on Genetic and Evolutionary Computing (ICGEC),2010:775-778.
[30]Rashid R A, Arifin S, Rahim M, Sarijari M A, Mahalin N H. Home Healthcare Via Wireless Biomedical Sensor Network [C]. IEEE International RF and Microwave Conference (RFM),2008:511-514.
[31]Karl H, Willig A. Protocols and Architectures for Wireless Sensor Networks [M]. John Wiley & Sons,2007.
[32]Muthukarpagam S, Niveditta V, Neduncheliyan S. Design Issues, Topology Issues, Quality of Service Support for Wireless Sensor Networks:Survey and Research Challenges [J]. International Journal of Computer Applications,2010, 1(6):1-4.
[33]卞永钊,于海斌,曾鹏.无线传感器网络中的拓扑控制[J].计算机应用研究,2008,25(10)：3128-3133.
[34]张志勇,胡光岷.无线传感器网络拓扑识别算法[J].计算机应用,2010,30(3)：733-735.
[35]Mendoza M L, Silva V H Z. Evaluation of Self-Organization Architecture for Special WSN Using Geometrical Arrays of Nodes. [C].1st International Conference on Computational Intelligence, Communication Systems and Networks,2009:137-142.
[36]Lu J L, Valois F, Barthel D, Dohler M. Fisco:A Fully Integrated Scheme of Self-Configuration and Self-Organization for WSN [C]. IEEE Wireless Communications & Networking Conference,2007:3372-3377.
[37]Khanna R, Liu H P, Chen H H. Self-Organization of Wireless Sensor Network for Autonomous Control in an It Server Platform [C]. IEEE International Conference on Communications,2010:1-5.
[38]Hou L, Wu M Q, Zhang Y. Energy Efficiency of Self-Organization Proposals in Wireless Sensor Network [C]. IEEE 70th Vehicular Technology Conference Fall, 2009:1475-1479.
[39]Gautam A K, Gautam A K. A Protocol for Energy Efficient, Location Aware, Uniform and Grid Based Hierarchical Organization of Wireless Sensor Networks [J]. Contemporary Computing,2009,40(6):273-283.
[40]Wang Y. Study on Model and Architecture of Self-Organization Wireless Sensor Network [C].4th International Conference on Wireless Communications, Networking and Mobile Computing,2008:3807-3810.
[41]Wang R, Liang Y, Ye H Q, Lu C X, Pan Q. Swarm Intelligence for the Self-Organization of Wireless Sensor Network [C]. IEEE Congress on Evolutionary Computation,2006:838-842.
[42]Kim D S, Chung Y J. Self-Organization Routing Protocol Supporting Mobile Nodes for Wireless Sensor Network [C].1st International Multi-Symposiums on Computer and Computational Sciences (IMSCCS 2006),2006:622-626.
[43]Cardei M, Du D Z. Improving Wireless Sensor Network Lifetime through Power Aware Organization [J]. Wireless Networks,2005,11 (3):333-340.
[44]Sohrabi K, Gao J, Ailawadhi V, Pottie G J. Protocols for Self-Organization of a Wireless Sensor Network [J]. IEEE Personal Communications,2000,7(5): 16-27.
[45]刘志新,袁会美,关新平,薛亮.传感器网络多路径传输效用一寿命折衷优化研究[J].传感技术学报,2009,22(10)：1465-1470.
[46]刘刚,彭力.基于节点能量均衡的无线传感器网络目标定位算法[J].计算机测量与控制,2011(7)：1804-1806.
[47]黄河,陈国良,孙玉娥,肖明军,黄刘生.复杂区域节点定位算法研究[J].计算机研究与发展,2011,48(3)：364-373.
[48]Lazos L, Poovendran R. Stochastic Coverage in Heterogeneous Sensor Networks [J]. ACM Transactions on Sensor Networks (TOSN),2006,2(3):325-358.
[49]Wang X, Xing G, Zhang Y, Lu C, Pless R, Gill C. Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks [C]. Proceedings of the 1st international conference on Embedded networked sensor systems,2003: 28-39.
[50]Basagni S, Chlamtac I, Syrotiuk V R, Woodward B A. A Distance Routing Effect Algorithm for Mobility (Dream) [C]. Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking,1998:76-84.
[51]Takagi H, Kleinrock L. Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals [J]. IEEE Transactions on Communications,1984,32(3): 246-257.
[52]Ko Y-B, Vaidya N H. Location-Aided Routing (Lar) in Mobile Ad Hoc Networks [J]. Wireless Networks,2000,6(4):307-321.
[53]Bose P, Morin P, Stojmenovic I, Urrutia J. Routing with Guaranteed Delivery in Ad Hoc Wireless Networks [J]. Wireless Networks,2001,7(6):609-616.
[54]Ahmed N, Kanhere S S, Jha S. The Holes Problem in Wireless Sensor Networks: A Survey [J]. ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(2):4-18.
[55]Li J, Mohapatra P. Analytical Modeling and Mitigation Techniques for the Energy Hole Problem in Sensor Networks [J]. Pervasive and Mobile Computing, 2007,3(3):233-254.
[56]郝晓辰,翟明,刘彬,张增仁.负载均衡的无线传感器网络拓扑控制算法[J].计算机工程,2009,35(5)：84-86.
[57]王敏,李士宁,李志刚.基于蚁群算法的WSN多路径负载均衡路由[J].计算机工程,2011,37(14)：1-4.
[58]Olariu S, Stojmenovic I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting [C].25th IEEE International Conference on Computer Communications (INFOCOM),2006:1-12.
[59]Akyildiz I F, Kasimoglu I H. Wireless Sensor and Actor Networks:Research Challenges [J]. Ad Hoc Networks,2004,2(4):351-367.
[60]Verdone R. Wireless Sensor and Actuator Networks:Technologies, Analysis and Design [M]. Elsevier/Academic Press,2008.
[61]Martinez D, Blanes F, Simo J, Crespo A. Wireless Sensor and Actuator Networks: Charecterization and Case Study for Confined Spaces Healthcare Applications [C]. International Multiconference on Computer Science and Information Technology (IMCSIT),2008:687-693.
[62]张重庆,李明禄,伍民友.数据收集传感器网络的负载平衡网络构建方法[J].软件学报,2007,18(5)：1110-1121.
[63]李巧勤,刘明,杨梅,陈贵海.负载相似节点分布解决传感器网络能量洞问题[J].软件学报,2011,22(3)：451-465.
[64]Fang Q, Gao J, Guibas L J. Locating and Bypassing Routing Holes in Sensor Networks [C].23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2004:2458-2468.
[65]Fang Q, Gao J, Guibas L. Locating and Bypassing Holes in Sensor Networks [J]. Mobile Networks and Applications,2006,11(2):187-200.
[66]Fekete S, Kroller A, Pfisterer D, Fischer S, Buschmann C. Neighborhood-Based Topology Recognition in Sensor Networks [M], in Algorithmic Aspects of Wireless Sensor Networks, S. Nikoletseas and J. Rolim, Editors,2004, Springer Berlin/Heidelberg:123-136.
[67]Wang Y, Gao J, Mitchell J S B. Boundary Recognition in Sensor Networks by Topological Methods [C]. Proceedings of the 12th annual international conference on Mobile computing and networking,2006:122-133.
[68]Kroller A, Fekete S P, Pfisterer D, Fischer S. Deterministic Boundary Recognition and Topology Extraction for Large Sensor Networks [C]. Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm, 2006:1000-1009.
[69]Ghrist R, Muhammad A. Coverage and Hole-Detection in Sensor Networks Via Homology [C]. Proceedings of the 4th international symposium on Information processing in sensor networks,2005:34.
[70]Saukh O, Sauter R, Gauger M, Marron P J. On Boundary Recognition without Location Information in Wireless Sensor Networks [J]. ACM Transactions on Sensor Networks (TOSN),2010,6(3):1-35.
[71]Funke S. Topological Hole Detection in Wireless Sensor Networks and Its Applications [C]. Proceedings of the 2005 joint workshop on Foundations of mobile computing (DIALM-POMC),2005:44-53.
[72]Simek M, Bocek J, Moravek P. Optimization of Boundary Recognition Algorithms for Wireless Sensor Network Applications [C].34th International Conference on Telecommunications and Signal Processing (TSP),2011:189194.
[73]朱永利,韩凯,张哲.WSN中数据传输瓶颈问题解决方案研究[J].微机与应用,2009,28(23)：36-39.
[74]田乐,谢东亮,韩冰,张雷,程时端.无线传感器网络中瓶颈节点的研究[J].软件学报,2006,17(4)：830-837.
[75]底欣,张百海.无线传感器网络瓶颈节点判断及路由方法研究[J].仪器仪表学报,2011,32(9)：1973-1980.
[76]Gou H, Yoo Y. Distributed Bottleneck Node Detection in Wireless Sensor Network [C]. IEEE 10th International Conference on Computer and Information Technology (CIT),2010:218-224.
[77]Gebhart B. Heat Conduction and Mass Diffusion [M]. McGraw-Hill,1993.
[78]管志成,李俊杰.常微分方程与偏微分方程[M].浙江大学出版社：杭州,2001.
[79]秦允豪.热学[M].2 ed.高等教育出版社：北京,2004.
[80]Cntr-Map-1.2008 [cited 2008 March 01]; [This is a contour map labeled according to accepted cartographic conventions. Labels are placed in a sligthly curved line stepping up to the summit from several directions.]. Available from:http://en.wikipedia.org/wiki/File:Cntr-map-1.jpg.
[81]Zhang R, Chen L, Guo J, Meng Z, Xu G. An Energy-Efficient Wireless Sensor Network Used for Farmland Soil Moisture Monitoring [C]. IET International Conference onWireless Sensor Network (IET-WSN),2010:2-6.
[82]Bruck J, Gao J, Jiang A. Map:Medial Axis Based Geometric Routing in Sensor Networks [J]. Wireless Networks,2007,13(6):835-853.
[83]Fang Q, Gao J, Guibas L J, de Silva V, Zhang L. Glider:Gradient Landmark-Based Distributed Routing for Sensor Networks [C].24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2005:339-350.
[84]Min R, Chandrakasan A. A Framework for Energy-Scalable Communication in High-Density Wireless Networks [C]. Proceedings of the 2002 international symposium on Low power electronics and design,2002:36-41.
[85]Raghunathan V, Schurgers C, Sung P, Srivastava M B. Energy-Aware Wireless Microsensor Networks [J]. Signal Processing Magazine, IEEE,2002,19(2): 40-50.
[86]Karpf-Cogan D. Distributed Wireless Sensor Networks (WSNs) Bottleneck Detection [D]. The Hebrew University of Jerusalem,2010.
[87]Zhu X J, Sarkar R, Gao J. Segmenting a Sensor Field:Algorithms and Applications in Network Design [J]. ACM Transactions on Sensor Networks (TOSN),2009,5(2):12:1-12:32.
[88]Dey T K, Giesen J, Goswami S. Shape Segmentation and Matching with Flow Discretization [C]. Proceedings of Workshop on Algorithms and Data Structures(WADS),2003:25-36.
[89]Sebastian T B, Klein P N, Kimia B B. Recognition of Shapes by Editing Their Shock Graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(5):550-571.
[90]Siddiqi K, Shokoufandeh A, Dickinson S J, Zucker S W. Shock Graphs and Shape Matching [J]. International Journal of Computer Vision,1999,35(1): 13-32.
[91]Hilaga M, Shinagawa Y, Kohmura T, Kunii T L. Topology Matching for Fully Automatic Similarity Estimation of 3d Shapes [C]. Proceedings of the 28th annual conference on Computer graphics and interactive techniques,2001: 203-212.
[92]Leymarie F F, Kimia B B. The Shock Scaffold for Representing 3d Shape [C]. Proceedings of the 4th International Workshop on Visual Form,2001:216-228.