无线传感器网络拓扑控制算法研究
|
摘要
无线传感器网络能够协作感知,采集网络分布区域内各种监测对象的信息,并对这些信息进行处理,最终传送到用户端,在新一代网络中具有关键性作用。由于传感器网络节点能量受限,为延长网络生存周期,拓扑控制算法成为近年来无线传感器网络的研究热点。这类算法的作用是通过种种手段对网络拓扑进行改造,减小节点的能耗,延长网络的生存周期。无线传感器网络的另一特点是没有基站一类的基础设施,众多节点在软硬件上同构,通过自组织而形成网络。分布式算法非常适合这一特点。因此,本文重点研究基于本地信息的分布式拓扑控制算法。我们称基于常数跳内收集到的信息而运行的算法为本地化算法。
拓扑控制算法改造网络拓扑的方式主要有两大类：一种是通过调整节点发射功率来减小节点能耗,降低通信干扰。另一种是通过构造骨干网将网络分层,网络中的节点轮流负责转发数据,均衡节点间能量消耗,延长网络寿命。前一类算法形成的网络拓扑是平面的,后一类算法构造了层次型的拓扑。
通过研究拓扑形态对拓扑控制算法在网络生存周期内的能耗的影响,我们发现层次型的拓扑结构,使得算法的能耗更优,进一步的分析表明,树型结构的骨干网不能实现本地化维护,能耗较差。以这两个结论为依据,我们提出了构建网状的连通控制集作为骨干网的Meshed CDS算法,它在大多数情况下能够实现本地化拓扑维护,算法运行的能耗较低。
考虑到骨干网节点能耗高于其它节点,减小骨干网节点数量也是延长网络生存时间的必要手段。我们提出的网状连通控制集MESH-CDS算法,不但能够实现完全的本地化拓扑维护,而且骨干网节点数量相对于网状结构的连通控制集Meshed CDS算法大大减小。更有价值的是,该算法不需要节点在之间同步运行,这非常适合节点能量动态变化的无线传感器网络。
最后我们提出节点数量缩减的网状连通控制集DMESH-CDS算法,它优先选择节点度数更大的节点成为骨干网节点,在网状连通控制集MESH-CDS算法基础上对骨干网的大小做了进一步的削减。
Wireless sensor network (WSN) which is able to perceive and collect the information of objects under monitoring in the distribution of WSN, process and send them to the client, plays a key role in the next generation of networks. Since WSN is energy constrained, topology control algorithms which are designed to save energy have become the research hotspot in recent years. Topology control algorithms archieve their goals by making special modifications to the network topology. Another feature of WSN is that there is not any network infrastructure, such as base stations, in it. All the sensor nodes have been built equally in hardware and software, which makes them self-organized to form the network topology. Obviously, distributive algorithms are applicable to WSN. So, this article focuses on localized distributive algorithms of topology control. An algorithm which only needs information within a constant number of hops is called "localized".
Topology control algorithms modificate the network topology in mainly two ways:One way is to adjust the transmit power of sensor nodes, in order to save energy; the other one is to construct a backbone of network, which divide the nodes into different levels so that the energy consumption will be balanced among them. Finally, the lifetime of the network will be prolonged. We noticed that the first kind of algorithms make a flat topology as well as the latter kind makes a hierarchical network.
According to the research on the relationships between topology structure and energy cost of topology algorithms, we find that the hierarchical structures lead to a better performance on energy cost of algorithms. Further more, we conclude that the tree-type backbone has a large energy cost because there is no localized maintenance scheme. Under these two conlusions, we proposed an algorithm, "Meshed CDS", which makes a mesh connected dominating sets (CDS) to be the backbone. It has a low energy cost since in most cases, the backbone can be maintained using localized manner.
Reducing the number of backbone is essential for WSN because the backbone nodes on backbone consume more energy than the other nodes. We proposed a "MESH-CDS" algorithms which is not only has a completely localized topology maintenance scheme, but also much less number of backbone nodes. In addition, it can be run asynchronously among all the nodes in the network.
At last, we proposed an algorithm which is named "DMESH-CDS". This proposal selects the nodes with lager degrees to be backbone nodes. The simulation result shows that the backbone's size has been decreased compared with "MESH-CDS".
拓扑控制算法改造网络拓扑的方式主要有两大类：一种是通过调整节点发射功率来减小节点能耗,降低通信干扰。另一种是通过构造骨干网将网络分层,网络中的节点轮流负责转发数据,均衡节点间能量消耗,延长网络寿命。前一类算法形成的网络拓扑是平面的,后一类算法构造了层次型的拓扑。
通过研究拓扑形态对拓扑控制算法在网络生存周期内的能耗的影响,我们发现层次型的拓扑结构,使得算法的能耗更优,进一步的分析表明,树型结构的骨干网不能实现本地化维护,能耗较差。以这两个结论为依据,我们提出了构建网状的连通控制集作为骨干网的Meshed CDS算法,它在大多数情况下能够实现本地化拓扑维护,算法运行的能耗较低。
考虑到骨干网节点能耗高于其它节点,减小骨干网节点数量也是延长网络生存时间的必要手段。我们提出的网状连通控制集MESH-CDS算法,不但能够实现完全的本地化拓扑维护,而且骨干网节点数量相对于网状结构的连通控制集Meshed CDS算法大大减小。更有价值的是,该算法不需要节点在之间同步运行,这非常适合节点能量动态变化的无线传感器网络。
最后我们提出节点数量缩减的网状连通控制集DMESH-CDS算法,它优先选择节点度数更大的节点成为骨干网节点,在网状连通控制集MESH-CDS算法基础上对骨干网的大小做了进一步的削减。
Wireless sensor network (WSN) which is able to perceive and collect the information of objects under monitoring in the distribution of WSN, process and send them to the client, plays a key role in the next generation of networks. Since WSN is energy constrained, topology control algorithms which are designed to save energy have become the research hotspot in recent years. Topology control algorithms archieve their goals by making special modifications to the network topology. Another feature of WSN is that there is not any network infrastructure, such as base stations, in it. All the sensor nodes have been built equally in hardware and software, which makes them self-organized to form the network topology. Obviously, distributive algorithms are applicable to WSN. So, this article focuses on localized distributive algorithms of topology control. An algorithm which only needs information within a constant number of hops is called "localized".
Topology control algorithms modificate the network topology in mainly two ways:One way is to adjust the transmit power of sensor nodes, in order to save energy; the other one is to construct a backbone of network, which divide the nodes into different levels so that the energy consumption will be balanced among them. Finally, the lifetime of the network will be prolonged. We noticed that the first kind of algorithms make a flat topology as well as the latter kind makes a hierarchical network.
According to the research on the relationships between topology structure and energy cost of topology algorithms, we find that the hierarchical structures lead to a better performance on energy cost of algorithms. Further more, we conclude that the tree-type backbone has a large energy cost because there is no localized maintenance scheme. Under these two conlusions, we proposed an algorithm, "Meshed CDS", which makes a mesh connected dominating sets (CDS) to be the backbone. It has a low energy cost since in most cases, the backbone can be maintained using localized manner.
Reducing the number of backbone is essential for WSN because the backbone nodes on backbone consume more energy than the other nodes. We proposed a "MESH-CDS" algorithms which is not only has a completely localized topology maintenance scheme, but also much less number of backbone nodes. In addition, it can be run asynchronously among all the nodes in the network.
At last, we proposed an algorithm which is named "DMESH-CDS". This proposal selects the nodes with lager degrees to be backbone nodes. The simulation result shows that the backbone's size has been decreased compared with "MESH-CDS".
引文
[1]孙利民,李建中,陈渝,朱红松。无线传感器网络。北京：清华大学出版社,2005.
[2]Estrin D., Govindan R., Heidemann J. S., Kumar S. Next century challenges: Scalable coordinate in sensor network. In:Proc 5th ACM/IEEE Int'l Conf on Mobile Computing and Networking.1999.264-270
[3]Bonnet P., Gehreke J., Seshadri P. Querying the physical world. IEEE Personal Communication,2000,7(5):10-15
[4]Pottie G. J., Kaiser W. J. Embedding the Internet:Wireless integrated network sensors. Communications of the ACM,2000,43(5):51-58
[5]Akyildiz I. F., Su W., Sankarasubramaniam Y., Cayirci E. A survey on sensor networks. IEEE Communications Magazine,2002,40(8):102-104
[6]Pister K., Hohlt B., Jeong J., Doherty L., Vainio J. P. Ivy—A sensor network infrastructure. http://www-bsac.eecs.berkeley.edu/projects/ivy.2003
[7]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7)：1282～1291
[8]Rentala P., Musunuri R., Gandham S., Saxena U. Survey on sensor networks. Technical Report, UTDCS-33-02, University of Texas at Dallas,2002
[9]Estrin D. Tutorial "Wireless Sensor Networks" Part Ⅳ:Sensor Network Protocols. Mobicom 2002. http://nestl.ee.ucla.edu/tutorials/mobicom2002/ 2002
[10]Shih E., Cho S. H., Ickes N., Min R., Sinha A., Wang A., Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In:Proc 7th Annual Int'l Conf on Mobile Computing and Networking (Mobicom 2001).2001.272-287
[11]Sinha A., Chandrakasan A. Dynamic power management in wireless sensor network. IEEE Design and Test of Computer,2001,18(2):64-74
[12]University of California at Los Angeles. WINS:Wireless integrated network sensors. http://www.janet.ucla.edu/WINS/biblio.htm
[13]Govindan R., Hellerstein J., Hong W., Madden S., Franklin M., Shenker S. The sensor network as a database. Technical Report 02-771, Computer Science Department, University of Southern California,2002
[14]Warneke B., Last M., Liebowitz B., Pisker K. S. J. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer Magazine,2001,34(1):44-51
[15]Noury N., Herve T., Rialle V., Virone G., Mercier E. Monitoring behavior in home using a smart fall sensor and position sensors. In:Proc IEEE-EMBS Special Topic Conf on Microtechnologies in Medicine and Biology. Lyon, France.2000.607-610
[16]Heinzelman W. R., Chandrakasan A., Balakrishnan H. Energy-efficient communication protocol for wireless microsensor network. In:Proc 33rd Int'l Conf System Sciences (HISS'00), January 2000.1-10
[17]Sohrabi K., Gao J., Ailawadhi V., Pottie G. J. Protocol for self-organization of a wireless sensor network. IEEE Personal Communications, October 2000,16-27
[18]于海滨,曾鹏.分布式无线传感器网络协议研究.通信学报,2004,25(10)：102～110
[19]李建中,李金宝.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,14(10)：1717～1727
[1]Santi, P. Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys.vol 37.2005:164-194
[2]J. Diaz, M. D. Penrose, J. Petit, and M. Serna. Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs. Combinatorics, Probability, and Computing.6,2000:489-511.
[3]P. Gupta, P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W. M. McEneany, G. Yin, Q. Zhang. Stochastic Analysis, Control, Optimization and Applications, Boston, MA, 1998:547-566
[4]C. Bettstetter. On the Mimimum Node Degree and Connectivity of a Wireless Multihop Network. In Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc), Lausanne, Switzerland,2002.
[5]X. Y. Li, P. J. Wan, Y. Wang, and C. W. Yi. Fault Tolerant Deployment and Topology Control in Networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Annapolis, MD,2003.
[6]F. Xue and P. R. Kumar. The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks.10(2).2005:169-181.
[7]D. Blough, M. Leoncini, G. Resta, and P. Santi. The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Annapolis, MD,2003.
[8]A. D. Garey, D. S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. Oxford, UK. W. H. Freeman.1979.
[9]G. T. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition,12,1980:261-268.
[10]J. W. Jaromczyk, G. T. Toussanit. Relative neighborhood graphs and their relatives. Proc. IEEE,80(9),1992:1502-1517.
[11]N. Li, J. C. Hou. Topology control in heterogeneous wireless networks: Problems and solutions. In:Proc 13th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2004.
[12]N. Li, J. C. Hou, L. Sha. Design and analysis of an MST-based topology control algorithms. In:14th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2003.
[13]K.M.Alzoubi, P.J. Wan, and O. Frieder.Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks. JOURNAL OF COMMUNICATIONS AND NETWORKS,2002.4(1).
[14]任丰原,黄海宁,林闯。无线传感器网络。软件学报,vol.14,No.7.2003：1282～1290.
[15]P. J. Wan, K.M.Alzoubi,and O. Frieder. Distributed Constructionof Connected Dominating Set in Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM, New York, June 2002.
[16]S. Guha and S. Kullar. Approximation Algorithms for Connected Dominating Sets. Algorithmica, vol.20,1998:374-387.
[17]S.Basagni, M.Mastrogiovanni, and C.Petrioli.A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks. In:IEEE International Conference onMobile Ad-hoc and Sensor Systems.2004
[18]W.R.Heinzelman, A. Chandrakasan, H.Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Annual Hawaii International Conference onSystem Sciences. 2000.
[19]O. Younis, S. Fahmy. Distributed clustering in ad hoc sensor networks:A hybrid, energy-efficient approach. In:Proc 13th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2004.
[20]J. Wu and H. Li.On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999 T. J. Kwon and M. Gerla. Clustering with Power Control. In Proceedings of MILCOM. Atlantic City, NJ.1999:1424-1428, vol.2.
[21]C. Chiasserini, I. Chlamatac, P. Monti and A. Nucci. Energy-Efficient Design of Wireless Ad hoc Networks. In Proceedings of the IFIP Networking. Pisa, Italy.2002.
[22]V. Kawadia and P. R. Kumar. Power Control and Clustering in Ad Hoc Networks. In Proceedings of IEEE INFOCOM. San Francisco, CA. March. 2003.
[23]Y. Xu, J. Heidemann, D. Estrin. Geography-Informed Energy Conservation for Ad Hoc Routing. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (Mobicom). Rome, Italy.2001:70-84.
[24]A. Cerpa and D. Estrin. ASCENT:Adaptive Self-Configuring Sensor Networks Topologies. In Proceedings of the INFOCOM. New York.2002.
[25]孙利民,李建中,陈渝,朱红松。无线传感器网络。北京：清华大学出版社,2005.
[26]Holger Karl, Andreas Willig. Protocols and Architectures for Wireless Sensor Networks北京：电子工业出版社,2007.
[1]Basagni, S. and Mastrogiovanni, M. and Petrioli, C.A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks.2004 IEEE International Conference onMobile Ad-hoc and Sensor Systems.2004.
[2]Hester, L.; Huang, Y.; Andric, O.; Allen, A.& P.Chen neuRFon Netform:A Self-Organizing Wireless Sensor Network Eleventh International Conference on Computer Communications and Networks,2002. Proceedings.,2002: 364-369
[3]Basagni, S. Distributed Clustering for Ad Hoc Networks. In Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks.1999.
[4]Heinzelman, W.R.; Chandrakasan, A.& Balakrishnan, H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks.In Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), 2000:3005-3014
[5]Pan, Jianping and Hou, Y. Thomas and Cai, Lin and Shi, Yi and Shen, Sherman X.Topology control for wireless sensor networks. In Proceedings of the 9th annual international conference on Mobile computing and networking (MobiCom).2003.
[6]Chalermek, D.E. Directed Diffusion:A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom). 2000:56-67
[7]J. Wu and H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999
[8]Amis, A. D. et al. Max-Min D-Cluster Formation in Wireless Ad Hoc Networks.In Proc. IEEE INFOCOM, Mar.2000:32-41
[9]Banerjee, S. and Khuller,S.A Clustering Scheme for Hierarchical Control in Multihop Wireless Networks. In Proc. IEEE INFOCOM, Apr.2001: 1028-1037
[10]Heinzelman, W.,. Chandrakasan, A. and H. Balakrishnan, An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Trans. Wireless Communications., vol.(1), no.4, Oct. 2002:660-70
[11]Hichem, M. and Hamamache, K. Distributed algorithms for Constructing and Maintaning a Spanning Tree in a Mobile Ad hoc Network, rtp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-165/paperl2.pdf
[12]Xiang-Yang Li, Calinescu, G. and Peng-Jun WanDistributed construction of a planar spanner and routing for ad hoc wireless networks. In Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).2002.
[13]Brent N. Clark and Charles J. Colbourn and David S. Johnson, Unit disk graphs. Discrete Mathematics. vol.(86).1990:165-177.
[14]Seema Bandyopadhyay and Coyle, E.J.An energy efficient hierarchical clustering algorithm for wireless sensor networks. In Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).2003.
[15]Seema Bandyopadhyay and Coyle, E.J.Minimizing communication costs in hierarchically-clustered networks of wireless sensors. Computer Networks. vol.(44).2004:1-16.
[16]Lin, C.R. and Gerla, M.Adaptive clustering for mobile wireless networks. IEEE Journal onSelected Areas in Communications. vol.(15). 1997:(1265-1275).
[17]Gerla, Mario and Tzu-Chieh Tsai, Jack. Multicluster, mobile, multimedia radio network. Wireless Networks, vol.(1).1995:(255-265).
[18]Alzoubi,K. M., Wan,P.-J.and Frieder.O. Distributed heuristics for connected dominating set in wireless ad hoc networks. KICS Journal of Communications and Networks,4(1), March 2002
[19]Khan, M. and Pandurangan, G. and Anil Kumar, V.S.Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks. IEEE Transactions onParallel and Distributed Systems. vol.(20).2009:124-139
[20]Hamid, B. et.al. M.A Simple Distributed Algorithm for the Maintenance of a Spanning Tree. In Proceedings of VECoS.2007
[21]Cheng, C. and Cimet, I. and Kumar, S.A protocol to maintain a minimum spanning tree in a dynamic topologyACM.1998
[1]Xiuzhen Cheng and Min Ding and Dechang Chen. An approximation algorithm for connected dominating set in ad hoc networks. In Proc. of International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor, and Peerto-Peer Networks.2004.
[2]GuhaS. and Kullar.S.Approximation Algorithms for Connected Dominating Sets. Algorithmica, vol.20,1998:374-387.
[3]Alzoubi,K. M., Wan,P.-J. and Frieder.O. Distributed heuristics for connected dominating set in wireless ad hoc networks. KICS Journal of Communications and Networks,4(1), March 2002
[4]Alzoubi, Khaled M. and Wan, Peng-Jun and Frieder, Ophir. Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking(MobiHoc '02).2002.
[5]Cardei, Mihaela and Cheng, Xiaoyan and Cheng, Xiuzhen and zhu Du, Ding. Connected Domination in Multihop Ad Hoc Wireless Networks. In Proc. the 6th Interna Conference on Computer Science and Informatics.2002.
[6]Feng Wang, Thai, M.T., Ding-Zhu Du, On the construction of 2-connected virtual backbone in wireless networks. Wireless Communications, March 2009.
[7]Chatterjee, M., S.K. Das, and D. Turgut, WCA:A Weighted Clustering Algorithm for Mobile Ad Hoc Networks. Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks),2002. vol.5:p. pp.193--204.
[8]Basagni, S., C. Petrioli, and R. Petroccia, Efficiently reconFigureureurable backbones for wireless sensor networks. Computer Communications,2008. 31(4):668-698.
[9]J. Wu and H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999
[10]Basagni, S., Mastrogiovanni, M. and Petrioli, C.:A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks, Mobile Ad-hoc and Sensor Systems,2004 IEEE International Conference,2004
[2]Estrin D., Govindan R., Heidemann J. S., Kumar S. Next century challenges: Scalable coordinate in sensor network. In:Proc 5th ACM/IEEE Int'l Conf on Mobile Computing and Networking.1999.264-270
[3]Bonnet P., Gehreke J., Seshadri P. Querying the physical world. IEEE Personal Communication,2000,7(5):10-15
[4]Pottie G. J., Kaiser W. J. Embedding the Internet:Wireless integrated network sensors. Communications of the ACM,2000,43(5):51-58
[5]Akyildiz I. F., Su W., Sankarasubramaniam Y., Cayirci E. A survey on sensor networks. IEEE Communications Magazine,2002,40(8):102-104
[6]Pister K., Hohlt B., Jeong J., Doherty L., Vainio J. P. Ivy—A sensor network infrastructure. http://www-bsac.eecs.berkeley.edu/projects/ivy.2003
[7]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7)：1282～1291
[8]Rentala P., Musunuri R., Gandham S., Saxena U. Survey on sensor networks. Technical Report, UTDCS-33-02, University of Texas at Dallas,2002
[9]Estrin D. Tutorial "Wireless Sensor Networks" Part Ⅳ:Sensor Network Protocols. Mobicom 2002. http://nestl.ee.ucla.edu/tutorials/mobicom2002/ 2002
[10]Shih E., Cho S. H., Ickes N., Min R., Sinha A., Wang A., Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In:Proc 7th Annual Int'l Conf on Mobile Computing and Networking (Mobicom 2001).2001.272-287
[11]Sinha A., Chandrakasan A. Dynamic power management in wireless sensor network. IEEE Design and Test of Computer,2001,18(2):64-74
[12]University of California at Los Angeles. WINS:Wireless integrated network sensors. http://www.janet.ucla.edu/WINS/biblio.htm
[13]Govindan R., Hellerstein J., Hong W., Madden S., Franklin M., Shenker S. The sensor network as a database. Technical Report 02-771, Computer Science Department, University of Southern California,2002
[14]Warneke B., Last M., Liebowitz B., Pisker K. S. J. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer Magazine,2001,34(1):44-51
[15]Noury N., Herve T., Rialle V., Virone G., Mercier E. Monitoring behavior in home using a smart fall sensor and position sensors. In:Proc IEEE-EMBS Special Topic Conf on Microtechnologies in Medicine and Biology. Lyon, France.2000.607-610
[16]Heinzelman W. R., Chandrakasan A., Balakrishnan H. Energy-efficient communication protocol for wireless microsensor network. In:Proc 33rd Int'l Conf System Sciences (HISS'00), January 2000.1-10
[17]Sohrabi K., Gao J., Ailawadhi V., Pottie G. J. Protocol for self-organization of a wireless sensor network. IEEE Personal Communications, October 2000,16-27
[18]于海滨,曾鹏.分布式无线传感器网络协议研究.通信学报,2004,25(10)：102～110
[19]李建中,李金宝.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,14(10)：1717～1727
[1]Santi, P. Topology control in wireless ad hoc and sensor networks. ACM Computing Surveys.vol 37.2005:164-194
[2]J. Diaz, M. D. Penrose, J. Petit, and M. Serna. Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs. Combinatorics, Probability, and Computing.6,2000:489-511.
[3]P. Gupta, P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W. M. McEneany, G. Yin, Q. Zhang. Stochastic Analysis, Control, Optimization and Applications, Boston, MA, 1998:547-566
[4]C. Bettstetter. On the Mimimum Node Degree and Connectivity of a Wireless Multihop Network. In Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc), Lausanne, Switzerland,2002.
[5]X. Y. Li, P. J. Wan, Y. Wang, and C. W. Yi. Fault Tolerant Deployment and Topology Control in Networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Annapolis, MD,2003.
[6]F. Xue and P. R. Kumar. The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks.10(2).2005:169-181.
[7]D. Blough, M. Leoncini, G. Resta, and P. Santi. The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Annapolis, MD,2003.
[8]A. D. Garey, D. S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. Oxford, UK. W. H. Freeman.1979.
[9]G. T. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition,12,1980:261-268.
[10]J. W. Jaromczyk, G. T. Toussanit. Relative neighborhood graphs and their relatives. Proc. IEEE,80(9),1992:1502-1517.
[11]N. Li, J. C. Hou. Topology control in heterogeneous wireless networks: Problems and solutions. In:Proc 13th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2004.
[12]N. Li, J. C. Hou, L. Sha. Design and analysis of an MST-based topology control algorithms. In:14th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2003.
[13]K.M.Alzoubi, P.J. Wan, and O. Frieder.Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks. JOURNAL OF COMMUNICATIONS AND NETWORKS,2002.4(1).
[14]任丰原,黄海宁,林闯。无线传感器网络。软件学报,vol.14,No.7.2003：1282～1290.
[15]P. J. Wan, K.M.Alzoubi,and O. Frieder. Distributed Constructionof Connected Dominating Set in Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM, New York, June 2002.
[16]S. Guha and S. Kullar. Approximation Algorithms for Connected Dominating Sets. Algorithmica, vol.20,1998:374-387.
[17]S.Basagni, M.Mastrogiovanni, and C.Petrioli.A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks. In:IEEE International Conference onMobile Ad-hoc and Sensor Systems.2004
[18]W.R.Heinzelman, A. Chandrakasan, H.Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Annual Hawaii International Conference onSystem Sciences. 2000.
[19]O. Younis, S. Fahmy. Distributed clustering in ad hoc sensor networks:A hybrid, energy-efficient approach. In:Proc 13th Joint Conf on IEEE Computer and Communications Societies (INFOCOM).2004.
[20]J. Wu and H. Li.On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999 T. J. Kwon and M. Gerla. Clustering with Power Control. In Proceedings of MILCOM. Atlantic City, NJ.1999:1424-1428, vol.2.
[21]C. Chiasserini, I. Chlamatac, P. Monti and A. Nucci. Energy-Efficient Design of Wireless Ad hoc Networks. In Proceedings of the IFIP Networking. Pisa, Italy.2002.
[22]V. Kawadia and P. R. Kumar. Power Control and Clustering in Ad Hoc Networks. In Proceedings of IEEE INFOCOM. San Francisco, CA. March. 2003.
[23]Y. Xu, J. Heidemann, D. Estrin. Geography-Informed Energy Conservation for Ad Hoc Routing. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (Mobicom). Rome, Italy.2001:70-84.
[24]A. Cerpa and D. Estrin. ASCENT:Adaptive Self-Configuring Sensor Networks Topologies. In Proceedings of the INFOCOM. New York.2002.
[25]孙利民,李建中,陈渝,朱红松。无线传感器网络。北京：清华大学出版社,2005.
[26]Holger Karl, Andreas Willig. Protocols and Architectures for Wireless Sensor Networks北京：电子工业出版社,2007.
[1]Basagni, S. and Mastrogiovanni, M. and Petrioli, C.A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks.2004 IEEE International Conference onMobile Ad-hoc and Sensor Systems.2004.
[2]Hester, L.; Huang, Y.; Andric, O.; Allen, A.& P.Chen neuRFon Netform:A Self-Organizing Wireless Sensor Network Eleventh International Conference on Computer Communications and Networks,2002. Proceedings.,2002: 364-369
[3]Basagni, S. Distributed Clustering for Ad Hoc Networks. In Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks.1999.
[4]Heinzelman, W.R.; Chandrakasan, A.& Balakrishnan, H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks.In Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), 2000:3005-3014
[5]Pan, Jianping and Hou, Y. Thomas and Cai, Lin and Shi, Yi and Shen, Sherman X.Topology control for wireless sensor networks. In Proceedings of the 9th annual international conference on Mobile computing and networking (MobiCom).2003.
[6]Chalermek, D.E. Directed Diffusion:A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom). 2000:56-67
[7]J. Wu and H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999
[8]Amis, A. D. et al. Max-Min D-Cluster Formation in Wireless Ad Hoc Networks.In Proc. IEEE INFOCOM, Mar.2000:32-41
[9]Banerjee, S. and Khuller,S.A Clustering Scheme for Hierarchical Control in Multihop Wireless Networks. In Proc. IEEE INFOCOM, Apr.2001: 1028-1037
[10]Heinzelman, W.,. Chandrakasan, A. and H. Balakrishnan, An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Trans. Wireless Communications., vol.(1), no.4, Oct. 2002:660-70
[11]Hichem, M. and Hamamache, K. Distributed algorithms for Constructing and Maintaning a Spanning Tree in a Mobile Ad hoc Network, rtp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-165/paperl2.pdf
[12]Xiang-Yang Li, Calinescu, G. and Peng-Jun WanDistributed construction of a planar spanner and routing for ad hoc wireless networks. In Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).2002.
[13]Brent N. Clark and Charles J. Colbourn and David S. Johnson, Unit disk graphs. Discrete Mathematics. vol.(86).1990:165-177.
[14]Seema Bandyopadhyay and Coyle, E.J.An energy efficient hierarchical clustering algorithm for wireless sensor networks. In Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).2003.
[15]Seema Bandyopadhyay and Coyle, E.J.Minimizing communication costs in hierarchically-clustered networks of wireless sensors. Computer Networks. vol.(44).2004:1-16.
[16]Lin, C.R. and Gerla, M.Adaptive clustering for mobile wireless networks. IEEE Journal onSelected Areas in Communications. vol.(15). 1997:(1265-1275).
[17]Gerla, Mario and Tzu-Chieh Tsai, Jack. Multicluster, mobile, multimedia radio network. Wireless Networks, vol.(1).1995:(255-265).
[18]Alzoubi,K. M., Wan,P.-J.and Frieder.O. Distributed heuristics for connected dominating set in wireless ad hoc networks. KICS Journal of Communications and Networks,4(1), March 2002
[19]Khan, M. and Pandurangan, G. and Anil Kumar, V.S.Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks. IEEE Transactions onParallel and Distributed Systems. vol.(20).2009:124-139
[20]Hamid, B. et.al. M.A Simple Distributed Algorithm for the Maintenance of a Spanning Tree. In Proceedings of VECoS.2007
[21]Cheng, C. and Cimet, I. and Kumar, S.A protocol to maintain a minimum spanning tree in a dynamic topologyACM.1998
[1]Xiuzhen Cheng and Min Ding and Dechang Chen. An approximation algorithm for connected dominating set in ad hoc networks. In Proc. of International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor, and Peerto-Peer Networks.2004.
[2]GuhaS. and Kullar.S.Approximation Algorithms for Connected Dominating Sets. Algorithmica, vol.20,1998:374-387.
[3]Alzoubi,K. M., Wan,P.-J. and Frieder.O. Distributed heuristics for connected dominating set in wireless ad hoc networks. KICS Journal of Communications and Networks,4(1), March 2002
[4]Alzoubi, Khaled M. and Wan, Peng-Jun and Frieder, Ophir. Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking(MobiHoc '02).2002.
[5]Cardei, Mihaela and Cheng, Xiaoyan and Cheng, Xiuzhen and zhu Du, Ding. Connected Domination in Multihop Ad Hoc Wireless Networks. In Proc. the 6th Interna Conference on Computer Science and Informatics.2002.
[6]Feng Wang, Thai, M.T., Ding-Zhu Du, On the construction of 2-connected virtual backbone in wireless networks. Wireless Communications, March 2009.
[7]Chatterjee, M., S.K. Das, and D. Turgut, WCA:A Weighted Clustering Algorithm for Mobile Ad Hoc Networks. Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks),2002. vol.5:p. pp.193--204.
[8]Basagni, S., C. Petrioli, and R. Petroccia, Efficiently reconFigureureurable backbones for wireless sensor networks. Computer Communications,2008. 31(4):668-698.
[9]J. Wu and H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks. DIALM '99:Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications.1999
[10]Basagni, S., Mastrogiovanni, M. and Petrioli, C.:A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks, Mobile Ad-hoc and Sensor Systems,2004 IEEE International Conference,2004