无线Ad Hoc网络拓扑控制技术研究
|
摘要
无线Ad Hoc网络是一种充满发展潜力的无线网络通信系统,该网络具有的自组织、自配置、自适应以及自愈能力使之能够灵活地用于各种无任何固定通信基础设施支撑的环境。在影响无线Ad Hoc网络性能的众多因素之中,网络的拓扑结构是不可忽视的一个重要方面,因此如何优化Ad Hoc网络的拓扑结构、增强网络拓扑的容错能力并为上层通信协议提供良好的底层拓扑支撑是拓扑控制技术研究的重点。本文从基于能量平衡的分布式拓扑控制技术、关键传输半径问题以及高效的拓扑探测技术三个方面对Ad Hoc网络拓扑控制技术进行研究,并讨论了无线传感器网络MAC地址的分配问题,具体研究成果如下:
1.针对现有大多数拓扑控制机制不能有效平衡网络节点能量消耗的问题,本文提出了一种基于能量感知的分布式拓扑控制算法EDTC(Energy-aware Dynamic Topology Control)。通过引入综合反映能量消耗及剩余能量两方面因素的链路代价函数,EDTC能够根据节点能量的实时变化动态优化网络的拓扑结构。同时,无需获取精确的地理位置信息,节点仅根据网络局部区域内的拓扑信息即可确定所需的传输功率,从而完成对全局拓扑结构的优化,极大地降低了算法实现时的复杂度及开销。该算法是一种局部化,轻量级的拓扑控制机制。
2.在EDTC算法的基础之上,本文将动态进行拓扑优化的设计思想推广到异质无线Ad Hoc网络,提出了ESATC(Energy-aware Self-Adjust Topology Control)算法。该算法更具一般性,能够用于由多种节点混合组成的无线Ad Hoc网络。理论分析及仿真结果表明,与EDTC算法相同,ESATC算法能够构建具有连通性以及最小代价特性的网络拓扑结构,能够显著地延长网络的“寿命”。
3.关键传输半径不仅能够保持网络的连通性,而且能够减小节点的能量消耗和多址干扰,最大化网络容量。为了有效构建具有容错能力的网络拓扑结构,本文主要针对有较广应用范围的一维无线Ad Hoc网络,研究了以一定概率保障其拓扑二连通性的关键传输半径问题。从对网络割点出现概率的分析入手,基于独立性假设,给出了网络二连通概率与网络分布区域大小、节点数目、通信半径间的解析关系。仿真实验表明理论值与仿真值吻合良好,验证了所得结果的正确性。在实际工程中利用所得结论可以合理配置网络参数,从而改善网络拓扑结构在连通性方面的容错能力。
4.通过拓扑分割探测的方法预先发现网络连通关系中的薄弱环节,对保障多跳Ad Hoc网络端到端通信具有十分重要的意义。针对网络中极易导致网络拓扑分割的关键节点,本文首先证明了关键节点的判定准则,它从本质上揭示了关键节点i的产生与两个决定性因素(邻节点度Ni以及基本回路度Mi)间的关系,指出Ni-Mi≥2是关键节点i存在的充要条件,极大地方便了关键节点的判定。在此基础之上,结合Ad Hoc网络具体应用背景,提出了一种分布式拓扑分割探测算法DPDP(Distributed Partition Detection Protocol)。通过在局部范围内进行关键节点的探测,该算法能够有效达到网络拓扑分割探测目的。理论分析及实验结果表明:DPDP算法具有复杂度低、准确度高、开销小、扩展性好的特点,与其它算法相比具有较优的性能。
5.针对无线传感器网络MAC地址开销较大的问题,本文提出了一种适用于传感器网络的分布式MAC地址分配算法VGSR(Virtual Grid Spatial Reusing)。该算法将网络分布区域划分为一系列虚拟小区,并建立节点地理位置坐标与虚拟小区间的映射关系,通过MAC地址在不同虚拟小区处的空间复用达到减小节点MAC地址长度的目的。通过调整传感器节点的通信半径,VGSR算法能够在不失网络连通性的同时最大限度地降低MAC地址域的大小。理论分析和实验结果表明,该算法能够很好地适应网络规模的变化,具有消耗能量低和效率改善明显的特点,其性能优于现有的其他算法。
Wireless Ad Hoc network is formed by a collection of mobile, wireless devices that cooperatively route packets for each other without any aid of fixed infrastructure or centralized administration, and is a self-organizing and self-configuring multi-hop wireless communication system. In such a type of network, topology structure which is determined by the node position and transmission range has significant effect on network performance. Therefore, how to optimize network structure and enhance network survivability so as to provide underlying topology with desired property for upper layer communication protocol is major concern of topology control technology. In this dissertation, the topology control technology for wireless Ad Hoc networks is studied in three aspects: energy-based distributed topology control, critical transmitting range and topology partition detection. Meanwhile, MAC address assignment problem for wireless sensor networks is also discussed. The main achievements and results of this dissertation are listed as follows:
1. To address the problem that most of existing algorithms can not balance energy consumption and extend network lifetime efficiently, a lightweight dynamic topology control algorithm EDTC (Energy-aware Dynamic Topology Control) is proposed. Based on the link metric reflecting both the energy consumption rates and residual energy levels at the two end nodes, EDTC generates a dynamic network topology that changes with the variation of node energy. In addition, without the aid of location information, each node determines its transmission power according to local network information, which reduces the complexity and overhead greatly.
2. Based on EDTC, a localized distributed topology control algorithm called ESATC (Energy-aware Self-Adjusted Topology Control) is proposed for heterogeneous wireless Ad Hoc networks. It extends the idea of dynamic optimization into hybrid wireless networks and becomes more generalized. Theoretic analysis and experiment results show that just like EDTC, ESATC algorithm preserves network connectivity and minimum-cost property and it can extend network lifetime remarkably.
3. Biconnectivity is the baseline graph theoretic metric of fault tolerance to node failures which can keep network connectivity while allowing unexpected node failures. In this dissertation this property for one-dimensional wireless Ad Hoc networks with finite nodes is analyzed. With common adopted assumption of uniform node distribution for static networks, the formula for the critical transmitting range that realizes network biconnectivity with certain probability is derived via proposed independency approximation assumptions. Simulation results validate the accuracy of our conclusion and confirm its efficiency in practical network design.
4. As the failure of a critical node will directly partition a network, a theorem for critical node identification is proved, which indicates that node degree Ni and elementary loop degree Mi of node i are two decisive factors for the existence of a critical node and shows that Ni-Mi≥2 is the necessary and sufficient condition for node i being critical. Based on the theorem, a distributed topology partition detection algorithm called DPDP (Distributed Partition Detection Protocol) is presented for large scale networks, which achieves the goal of partition detection efficiently by detecting critical nodes in a local area. Theoretic analysis and experiment results show that DPDP has the advantages of low complexity, high accuracy, low cost as well as good scalability, and is superior to other algorithms.
5. Compared with the small overhead of data payload in wireless sensor network, the overhead of MAC address is significant in terms of energy-saving. In this dissertation, a novel distributed MAC address assignment algorithm named VGSR (Virtual Grid Spatial Reusing) is proposed, which reduces the size of the MAC address efficiently based on both the spatial reuse of MAC addresses and the mapping of geographical position. By adjusting the communication range of sensor nodes, VGSR can minimize the size of MAC address and meanwhile guarantee the connectivity of sensor network. The theoretic analysis and experiment result show that VGSR is low energy cost, but also it scales well with the network size. Its performance is superior to other existing algorithm.
1.针对现有大多数拓扑控制机制不能有效平衡网络节点能量消耗的问题,本文提出了一种基于能量感知的分布式拓扑控制算法EDTC(Energy-aware Dynamic Topology Control)。通过引入综合反映能量消耗及剩余能量两方面因素的链路代价函数,EDTC能够根据节点能量的实时变化动态优化网络的拓扑结构。同时,无需获取精确的地理位置信息,节点仅根据网络局部区域内的拓扑信息即可确定所需的传输功率,从而完成对全局拓扑结构的优化,极大地降低了算法实现时的复杂度及开销。该算法是一种局部化,轻量级的拓扑控制机制。
2.在EDTC算法的基础之上,本文将动态进行拓扑优化的设计思想推广到异质无线Ad Hoc网络,提出了ESATC(Energy-aware Self-Adjust Topology Control)算法。该算法更具一般性,能够用于由多种节点混合组成的无线Ad Hoc网络。理论分析及仿真结果表明,与EDTC算法相同,ESATC算法能够构建具有连通性以及最小代价特性的网络拓扑结构,能够显著地延长网络的“寿命”。
3.关键传输半径不仅能够保持网络的连通性,而且能够减小节点的能量消耗和多址干扰,最大化网络容量。为了有效构建具有容错能力的网络拓扑结构,本文主要针对有较广应用范围的一维无线Ad Hoc网络,研究了以一定概率保障其拓扑二连通性的关键传输半径问题。从对网络割点出现概率的分析入手,基于独立性假设,给出了网络二连通概率与网络分布区域大小、节点数目、通信半径间的解析关系。仿真实验表明理论值与仿真值吻合良好,验证了所得结果的正确性。在实际工程中利用所得结论可以合理配置网络参数,从而改善网络拓扑结构在连通性方面的容错能力。
4.通过拓扑分割探测的方法预先发现网络连通关系中的薄弱环节,对保障多跳Ad Hoc网络端到端通信具有十分重要的意义。针对网络中极易导致网络拓扑分割的关键节点,本文首先证明了关键节点的判定准则,它从本质上揭示了关键节点i的产生与两个决定性因素(邻节点度Ni以及基本回路度Mi)间的关系,指出Ni-Mi≥2是关键节点i存在的充要条件,极大地方便了关键节点的判定。在此基础之上,结合Ad Hoc网络具体应用背景,提出了一种分布式拓扑分割探测算法DPDP(Distributed Partition Detection Protocol)。通过在局部范围内进行关键节点的探测,该算法能够有效达到网络拓扑分割探测目的。理论分析及实验结果表明:DPDP算法具有复杂度低、准确度高、开销小、扩展性好的特点,与其它算法相比具有较优的性能。
5.针对无线传感器网络MAC地址开销较大的问题,本文提出了一种适用于传感器网络的分布式MAC地址分配算法VGSR(Virtual Grid Spatial Reusing)。该算法将网络分布区域划分为一系列虚拟小区,并建立节点地理位置坐标与虚拟小区间的映射关系,通过MAC地址在不同虚拟小区处的空间复用达到减小节点MAC地址长度的目的。通过调整传感器节点的通信半径,VGSR算法能够在不失网络连通性的同时最大限度地降低MAC地址域的大小。理论分析和实验结果表明,该算法能够很好地适应网络规模的变化,具有消耗能量低和效率改善明显的特点,其性能优于现有的其他算法。
Wireless Ad Hoc network is formed by a collection of mobile, wireless devices that cooperatively route packets for each other without any aid of fixed infrastructure or centralized administration, and is a self-organizing and self-configuring multi-hop wireless communication system. In such a type of network, topology structure which is determined by the node position and transmission range has significant effect on network performance. Therefore, how to optimize network structure and enhance network survivability so as to provide underlying topology with desired property for upper layer communication protocol is major concern of topology control technology. In this dissertation, the topology control technology for wireless Ad Hoc networks is studied in three aspects: energy-based distributed topology control, critical transmitting range and topology partition detection. Meanwhile, MAC address assignment problem for wireless sensor networks is also discussed. The main achievements and results of this dissertation are listed as follows:
1. To address the problem that most of existing algorithms can not balance energy consumption and extend network lifetime efficiently, a lightweight dynamic topology control algorithm EDTC (Energy-aware Dynamic Topology Control) is proposed. Based on the link metric reflecting both the energy consumption rates and residual energy levels at the two end nodes, EDTC generates a dynamic network topology that changes with the variation of node energy. In addition, without the aid of location information, each node determines its transmission power according to local network information, which reduces the complexity and overhead greatly.
2. Based on EDTC, a localized distributed topology control algorithm called ESATC (Energy-aware Self-Adjusted Topology Control) is proposed for heterogeneous wireless Ad Hoc networks. It extends the idea of dynamic optimization into hybrid wireless networks and becomes more generalized. Theoretic analysis and experiment results show that just like EDTC, ESATC algorithm preserves network connectivity and minimum-cost property and it can extend network lifetime remarkably.
3. Biconnectivity is the baseline graph theoretic metric of fault tolerance to node failures which can keep network connectivity while allowing unexpected node failures. In this dissertation this property for one-dimensional wireless Ad Hoc networks with finite nodes is analyzed. With common adopted assumption of uniform node distribution for static networks, the formula for the critical transmitting range that realizes network biconnectivity with certain probability is derived via proposed independency approximation assumptions. Simulation results validate the accuracy of our conclusion and confirm its efficiency in practical network design.
4. As the failure of a critical node will directly partition a network, a theorem for critical node identification is proved, which indicates that node degree Ni and elementary loop degree Mi of node i are two decisive factors for the existence of a critical node and shows that Ni-Mi≥2 is the necessary and sufficient condition for node i being critical. Based on the theorem, a distributed topology partition detection algorithm called DPDP (Distributed Partition Detection Protocol) is presented for large scale networks, which achieves the goal of partition detection efficiently by detecting critical nodes in a local area. Theoretic analysis and experiment results show that DPDP has the advantages of low complexity, high accuracy, low cost as well as good scalability, and is superior to other algorithms.
5. Compared with the small overhead of data payload in wireless sensor network, the overhead of MAC address is significant in terms of energy-saving. In this dissertation, a novel distributed MAC address assignment algorithm named VGSR (Virtual Grid Spatial Reusing) is proposed, which reduces the size of the MAC address efficiently based on both the spatial reuse of MAC addresses and the mapping of geographical position. By adjusting the communication range of sensor nodes, VGSR can minimize the size of MAC address and meanwhile guarantee the connectivity of sensor network. The theoretic analysis and experiment result show that VGSR is low energy cost, but also it scales well with the network size. Its performance is superior to other existing algorithm.
引文
[1]王金龙,王呈贵,吴启晖,龚玉萍. Ad Hoc移动无线网络.国防工业出版社,北京, 2003.
[2]罗涛,乐光新.多天线无线通信原理与应用.北京邮电大学出版社,北京, 2005.
[3]杨家玮,盛敏,刘勤.移动通信基础.电子工业出版社,北京, 2008.
[4]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术.电子工业出版社,北京, 2006.
[5] http://www.cctime.com/html/2008-5-26/2008526924582280.htm, 2008
[6]张克平. LET-B3G/4G移动通信系统无线技术.电子工业出版社,北京, 2008.
[7]李建东,杨家玮.个人通信.人民邮电出版社,北京, 1998.
[8] D. C. Cox,“Wireless personal communication: what is it?,”IEEE Personal Communications, vol. 2, no. 2, pp. 20-35, Apr. 1995.
[9] M. S. Gast. 802.11无线网络权威指南(影印版).清华大学出版社,北京, 2002.
[10] http://www.hsdcw.com/HTML/2008-5-14/116704.HTM, 2008.
[11] http://www.sasac.gov.cn/n1180/n1226/n2410/n314349/4537213.html, 2008.
[12] http://www.cww.net.cn/news/html/2008/5/23/2008523750468663.htm, 2008.
[13]于宏毅等.无线移动自组织网.人民邮电出版社,北京, 2005.
[14] Ram Ramanathan and Jason Radi,“A brief overview of ad hoc network: challenges and directions,”IEEE Communication Magazine, 50th Anniversary Commemorative Issue, pp. 20-22, May 2002.
[15] B. Xu and S. Hischke,“The role of ad hoc networking in future wireless communications,”in Proc. of International Conference on Communication Technology Proceedings (ICCT), Beijing, China, Apr. 2003, pp. 1353-1358.
[16]孙立民,李建中,陈渝,朱红松.无线传感器网络.清华大学出版社,北京, 2005.
[17]李建中,李金宝,石胜飞.传感器网络及数据管理的概念、问题与进展.软件学报, 2003, 14(10): 1717-1727.
[18] J. Jubin, J. D. Tornow,“The DARPA packet radio network protocols,”in Proc. of IEEE Special Issue on Packet Radio Networks, vol.75, no.1, Jan., 1987, pp.21-32.
[19] D. A. Beyer,“Accomplishments of the DARPA SURAN Program,”in Proc. of IEEE Military Communication Conference (IEEE MILCOM), Monterey, USA, Sept. 1990, pp. 855-862.
[20] B. M. Leiner, R. J. Ruth, A. R. Sastry,“Goals and challenges of the DARPA GloMo Program,”IEEE Personal Communications, vol.3, no.6, pp.34-43, Dec. 1996.
[21]何非常,周吉,李振邦.军事通信——现代战争的神经网络.国防工业出版社,北京, 2000.
[22] http://www.ieee802.org/11/.
[23] http://www.ietf.cnri.reston.va.us/html.charters/manet-charter.html.
[24] J. P. Macker, M. S. Corson,“Mobile ad hoc networking and the IETF,”ACM SIGMOBILE Mobile Computing and Communications Review, vol. 2, no. 2, pp. 9-14, Apr. 1998.
[25] J. Macker, S. Corson , B. Fenner, et al,“Mobile ad hoc networks,”http//www. ietf.Org/html.Charters/manet-charter.html.
[26] A. B. McDonald and T. F. Znati,“A mobility-based framework for adaptive clustering in wireless ad hoc networks,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp. 1466-1487, Aug. 1999.
[27] H. Q. Zhai, J. F. Wang, X. Chen, Y. G. Fang,“Medium access control in mobile ad hoc networks: challenges and solutions,”Wireless communications and Mobile Computing, vol. 6, no.2, pp. 151-170, Feb. 2006.
[28] E. S. Jung and N. H. Vaidya,“A power control MAC protocol for ad hoc networks,”Wireless Networks, vol.11, no.1-2, pp. 55-66, Jan. 2005.
[29] M. Mauve, A. Widmer, H. Hartenstein,“A survey on position-based routing in mobile ad hoc networks,”IEEE Network, vol.15, no.6, pp.30-39, Nov. 2001.
[30] R. Rajaraman,“Topology control and routing in ad hoc networks: a survey,”ACM SIGACT News, vol.33, no.2, pp. 60-73, June 2002.
[31]臧婉瑜,于勐,谢立,孙钟秀.按需式ad hoc移动网络路由协议的研究进展.计算机学报, 2002, 25(10): 1009-1017.
[32] A. Ahuja, S. Agarwal, J. P. Singh, R. Shorey,“Performance of TCP over different routing protocols in mobile ad hoc networks,”IEEE VTC-Spring, Tokyo, Japan, May 2000, pp. 2315-2319.
[33] W. Chen, N. Jain, S. Singh,“ANMP: ad hoc network management protocol,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp. 1506-1531, Aug. 1999.
[34]李云,赵为粮,隆克平,吴诗其.无线Ad Hoc网络支持QoS的研究进展与展望.软件学报, 2004, 15(12): 1885-1893.
[35] P. McDermott-Wells,“What is Bluetooth?,”IEEE Potentials, vol.23, no.5, pp. 33-35, Dec. 2004.
[36] D. Chen, S. Garg and K. S. Trivedi,“Network survivability performance evaluation: a quantitative approach with applications in wireless ad hoc networks,”in Proc. of MSWiM’02, Atlanta, USA, Spet. 2002, pp. 61-68.
[37] J. P. G. Sterbenz, R. Krishnan, et al,“Survivable mobile wireless networks: issues, challenges, and research directions,”in Proc. of the 1st ACM workshop on Wireless Security, Atlanta, USA, Sept. 2002, pp. 31-40.
[38] N. Li and J. C. Hou,“Topology control in heterogeneous wireless networks: problems and solutions,”IEEE INFOCOM, Hong Kong, China, Mar. 2004, pp. 232-242.
[39] I. Stojmenovic, M. Seddigh and J. Zunic,“Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks,”IEEE Trans. on Parallel and Distributed Systems, vol.13, no.1, pp. 14-25, Jan. 2002.
[40] S. Toumpis, A. Goldsmith,“Ad hoc network capacity,”in Proc. of the 34th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, Aug. 2000, pp. 1265-1269.
[41] P. Gupta, P. R. Kumar,“The capacity of wireless networks,”IEEE Trans. on Information Theory, vol.46, no.2, pp. 388-404, Mar. 2000.
[42] M. Cardei, J. Wu, S. Yang,“Topology control in ad hoc wireless networks using cooperative communication,”IEEE Trans. on Mobile Computing, vol.5, no.6, pp. 711-724, June 2006.
[43] V. Strvastava, M. Motani,“Cross-layer design: a survey and the road ahead,”IEEE Communications Magazine, vol.43, no.12, pp. 112-119, Dec. 2005.
[44] J. Gomez and A. T. Campbell,“Variable-range transmission power control in wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.6, no.1, pp. 87-99, Jan. 2007.
[45] P. Bose, P. Morin, I. Stojmenovic, J. Urrutia,“Routing with guaranteed delivery in ad hoc wireless networks,”Wireless Networks, vol.7, no.6, pp. 609-616, Nov. 2001.
[46] I. Stojmenovic,“Position-based routing in ad hoc networks,”IEEE Communications Magazine, vol.40, no.7, pp. 128-134, Jul. 2002.
[47] Paolo Santi. Topology Control in Wireless Ad Hoc and Sensor Networks. JohnWiley & Sons Ltd, England, 2005.
[48] Paolo Santi,“Topology control in wireless ad hoc and sensor networks,”ACM Computing Surveys, vol.37, no.2, pp.164-194, June 2005.
[49] A. A. Jeng and R. H. Jan,“An adaptive topology control scheme for energy-efficient routing in mobile ad hoc networks,”IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 4404-4407.
[50] L. Li and J. Y. Halpern,“A minimum-energy path-preserving topology-control algorithm,”IEEE Trans. on Wireless Communications, vol.3, no.3, pp.910-921, May 2004.
[51] A. Rahman, P. Gburzynski,“On constructing minimum-energy path-preserving graphs for ad-hoc wireless networks,”IEEE ICC, Seoul, Korea, May 2005, pp. 3083-3087.
[52] R. Basu and J. Redi,“Movement control algorithms for realization of fault-tolerant ad hoc robot networks,”IEEE Network, vol.18, no.4, pp.36-44, July-Aug. 2004.
[53] Z. Huang and C. Shen et al,“Topology control for ad hoc networks with directional antennas,”in Proc. of IEEE International Conference on Communication and Networks (ICCCN), Miami, USA, Oct. 2002, pp. 16-21.
[54] D. B. West. Introduction to Graph Theory, Second Edition. China Machine Press, Beijing, 2004.
[55] L. Kirousis, E. Kranakis, D. Krizanc, A. Pelc,“Power consumption in packet radio networks,”Theoretical Computer Science, vol.243, no.1-2, pp. 289-305, July 2000.
[56] A. Clementi, P. Penna, R. Silvestri,“Hardness results for the power range assignment problem in packet radio networks,”Lecture Notes in Computer Science, vol. 1671, pp. 197-208, 2004.
[57] T. H. Cormen, C. E. Leiserson, R. L. Rivest, et al. Introduction to Algorithms, Second Edition. Higher Education Press, Beijing, 2002.
[58] R. Ramanathan and R. Roasles-Hain,“Topology control of multihop wireless networks using transmit power adjustment,”IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp.404-413.
[59] E. L. Lloyd, R. Liu, M. V. Marathe, et al,“Algorithmic aspects of topology control problems for ad hoc networks,”ACM Mobihoc, Lausanne, Switzerland, June 2002, pp. 123-134.
[60] G. Y. Pei, M. Gerla, X. Y. Hong,“LANMAR: landmark routing for large scale wireless ad hoc networks with group mobility,”in Proc. of the 1st ACM international symposium on Mobile ad hoc networking & computing, Boston, USA, 2000, pp. 11-18.
[61] X. Y. Li, P. J. Wan and Y. Wang,“Power efficient and sparse spanner for wireless ad hoc networks,”in Proc. of the 10th International Conference on Computer Communications and Networks, Scottsdale, USA, Oct. 2001, pp. 564-567.
[62] A. A. Jeng and R. H. Jan,“The r-neighborhood graph: an adjustable structure for topology control in wireless ad hoc networks,”IEEE Trans. on Parallel and Distributed Systems, vol.18, no.4, pp. 536-549, April, 2007.
[63] Brad K, Kung H T,“GPSR: greedy perimeter stateless routing for wireless networks,”ACM MOBICOM, Boston, USA, Aug. 2000, pp.243-254.
[64] V. Rodoplu and T. H. Meng,“Minimum energy mobile wireless networks,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp.1333-1344, Aug. 1999.
[65] L. Li and J. Y. Halpern,“Minimum-energy mobile wireless networks revisited,”IEEE ICC, St. Petersburg, Russia, Jun. 2001, pp. 278-283.
[66] N. Li, J. Hou and L. Sha,“Design and analysis of an MST-based topology control algorithm,”IEEE Trans. on Wireless Communications, vol.4, no.3, pp. 1195-1206, May 2005.
[67] N. Li and J. Hou,“Localized fault-tolerant topology control in wireless ad hoc networks,”IEEE Trans. on Parallel and Distributed Systems, vol.17, no.4, pp. 307-320, April 2006.
[68] L. Li, J. Y. Halpern, P. Bahl, Y. Wang and R. Wattenhofer,“A cone-based distributed topology-control algorithm for wireless multi-hop networks,”IEEE/ACM Trans. on Networking, vol.13, no.1, pp. 147-159, Feb. 2005.
[69] M. Bahramgiri, M. Hajiaghayi and V. Mirrokni,“Fault-tolerant and 3-dimensional distrbuted topology control algorithms in wireless multi-hop networks,”in Proc. of International Conference on Communication and Networks (ICCCN), Miami, USA, Oct. 2002, pp.392-397.
[70] R. Wattenhofer and A. Zollinger,“XTC: a practical topology control for ad hoc networks,”in Proc. of 18th Parallel and Distributed Processing Symposium, Santa Fe, USA, Apr. 2004, pp.26-30.
[71]路纲,周明天,牛新征,佘堃,唐勇,秦科.无线网络邻近图综述.软件学报, 2008, 19(4): 888-911.
[72] G.. T. Toussaint,“The relative neighborhood grap of a finite planar set,”Pattern Recognition, vol.12, no. 4, pp. 261.268, 1980.
[73] K. R. Gabriel and R. R. Sokal,“A new statistical approach to geographic variation analysis,”Systematic Zoology, vol.18, pp.259-278, 1969.
[74] J. Geo, L. J. Guibas, J. Hershburger, L. Zhang and A. Zhu,“Geometric spanners for routing in mobile networks,”IEEE Journal on Selected Areas in Communications, vol.23, no.1, pp. 174-185, Jan. 2005.
[75] X. Y. Li, G. Calinescu, P. J. Wan and Y. Wang,“Localized delaunay triangulation with application in ad hoc wireless networks,”IEEE Trans. on Parallel and Distributed Systems, vol.14, no.10, pp. 1035-1047, Oct. 2003.
[76] A. C. C. Yao,“On constructing minimum spanning trees in k-dimensional spaces and related problems,”SIAM J. Computing, vol. 11, pp. 721-736, 1982.
[77] Y. Wang, X. Li and O. Frieder,“Distributed spanners with bounded degree for wireless ad hoc networks,”International Journal of Foundations of Computer Science, vol.14, no.2, pp. 183-200, 2002.
[78] W. Song, Y. Wang, X. Li and O. Frieder,“Localized algorithms for energy efficient topology in wireless ad hoc networks,”ACM MobiHoc, Tokyo, Japan, May 2004, pp. 98-108.
[79] C. E. Jones, K. M. Sivalingam, P. Agrawal and J. C. Chen,“A survey of energy efficient network protocols for wireless networks,”Wireless Networks, vol. 7, no.4, pp. 343-358, Aug. 2001.
[80] L. Li, J. Y. Halpern, P. Bahl, Y. M. Wang and R. Wattenhofer,“Analysis of a cone-based distributed topology control algorithm for wireless multihop networks,”in Proc. of ACM Symposium on Principles of Distributed Computing (PODC), Newport, USA, Aug. 2001, pp. 264-273.
[81] D. Blough, M. Leoncini, G. Resta and P. Santi,“The k-neighbors protocol for symmetric topology control in ad hoc networks,”in Proc. of ACM MobiHoc, Annapolis, USA, June 2003, pp. 141-152.
[82] Y. Shen, Y. Cai and X. M. Xu,“A shortest-path-based topology control algorithm in wireless multihop networks,”ACM SIGCOMM Computer Communication Review, vol. 37, no. 5, pp. 29-38, Oct. 2007.
[83] E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi,“Algorithmic aspects of topology control problems for ad hoc networks,”Mobile Networks and Applications, vol. 10, no. 1-2, pp. 19-34, Feb. 2005.
[84] Y. Cui, Y. Xue and K, Nahrstedt,“A utility-based distributed maximum lifetime routing algorithm for wireless networks,”IEEE Trans. Vehicular Technology, vol. 55, no.3, pp. 797-805, May 2006.
[85] H. Wang, Y. Yang and M. Ma,“Network lifetime global optimization by duality approach in wireless sensor networks,”IEEE GLOBECOM, Washington, DC, USA, Nov. 2007, pp. 1017-1021.
[86] A. Sankar, Z. Liu,“Maximum lifetime routing in wireless ad-hoc networks,”IEEE INFOCOM, Hong Kong, China, Mar. 2004, pp. 1089-1097.
[87] R. Zhang, M. A. Labrador,“Energy-aware topology control in heterogeneous wireless multi-hop networks,”in Proc. of the 2nd International Symposium on Wireless Pervasive Computing (ISWPC), San Juan, Puerto Rico, Feb. 2007, pp. 25-30.
[88] B. X. Zhang, Z. Zhao, J. Ma and H. T. Mouftah,“Efficient localized topology control algorithm,”in Proc. of International workshop on High Performance Switching and Routing (HPSR), New York, USA, June 2007, pp. 1-6.
[89] J. P. Sheu, S. C. Tu and C. H. Hsu,“Location-free topology control protocol in wireless ad hoc networks,”IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 66-71.
[90] R. S. Rappaport. Wireless Communications: Principles and Practice, Second Edition. Publishing House of Electronics Industry, Beijing, 2004.
[91] S. H. Lee, J. M. Choi and Y. B. Ko,“UAMAC: Unidirectional-link aware MAC protocol for heterogeneous ad hoc networks,”Ad-Hoc, Mobile, and Wireless Networks, vol. 3158, pp. 336-341, 2004.
[92] V. Ramasubramanian, D. Mosse,“BRA: A bidirectional routing abstraction for asymmetric mobile ad hoc networks,”IEEE/ACM Trans. Networking, vol. 16, no.1, pp. 116-129, Feb. 2008.
[93] J. L. Liu, B. C. Li,“Distributed topology control in wireless sensor networks with asymmetric links,”IEEE GLOBECOM, San Francisco, USA, Dec. 2003, pp. 1257-1262.
[94] http://en.wikipedia.org/wiki/Dijkstra's_algorithm.
[95] J. H. Chang, L. Tassiulas,“Maximum life routing in wireless sensor networks,”IEEE/ACM Trans. Networking, vol.12, no.4, pp. 609-619, Aug. 2004.
[96] X. J. Du, D. Wu, W. Liu and Y. G. Fang,“Multiclass routing and medium access control for heterogeneous mobile ad hoc networks,”IEEE Trans. Vehicular Technology, vol. 55, no.1, pp. 270-277, Jan. 2006.
[97] N. Li, J. and C. Hou,“Localized topology control algorithms for heterogeneouswireless networks,”IEEE/ACM Trans. Networking, vol.13, no.6, pp. 1313-1324, Dec. 2005.
[98] J. L. Liu, B. C. Li,“Distributed topology control in wireless sensor networks with asymmetric links,”IEEE GLOBECOM, San Francisco, USA, Dec. 2003, pp. 1257-1262.
[99] M. Penrose. Random Geometric Graphs. Oxford University Press, Oxford, 2003.
[100] M. Penrose,“The longest edge of the random minimal spanning tree,”The Annals of Applied Probability, vol.7, no.2, pp.340-361, 1997.
[101] M. Penrose,“Extremes for the minimal spanning tree on normally distributed points,”Advances in Applied Probability, vol.30, no.3, pp.628-639, 1998.
[102] M. Penrose,“On k-connectivity for a geometric random graph,”Random Structures and Algorithms, vol.15, no.2, pp.145-164, 1999.
[103] M. Penrose,“A strong law for the largest nearest–neighbour link between random points,”Journal of London Mathematical Society, vol.60, no.2, pp.951-960, 1999.
[104] M. Penrose,“A strong law for the largest edge of the minimal spanning tree,”The Annals of Probability, vol.27, no.1, pp.246-260, 1999.
[105] L. Holst,“On multiple covering of a circle with random arcs,”Journal of Applied Probability, vol.16, pp. 284-290, 1980.
[106] H. Dette, N. Henze,“The limit distribution of the largest nearest neighbor link in the unit d-cube,”Journal of Applied Probability, vol.26, pp. 67-80, 1989.
[107] P. Wan, C. Yi,“Asymptotical critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks,”ACM MobiHoc, Tokyo, Japan, May 2004, pp. 1-8.
[108] P. Santi and D. M. Blough,“The critical transmitting range for connectivity in sparse wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.2, no.1, pp. 25-39, 2003.
[109] P. Santi, D. M. Blough and F. Vainstein,“A probabilistic analysis for the range assignment problem in ad hoc networks,”ACM MobiHoc, Long Beach, USA, Oct. 2001, pp. 212-220.
[110] C. Bettstetter,“On the minimum node degree and connectivity of a wireless multihop network,”ACM MobiHoc, Lausanne, Switzerland, June 2002, pp.80-91.
[111] C. Bettstetter,“On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment,”IEEE VTC, Birmingham, USA,May 2002, pp.1706-1710.
[112] T. Camp, J. Boleng and V. Davies,“A survey of mobility for ad hoc network research,”Wireless Communication & Mobile Computing (WCMC), Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol.2, no.5, pp. 483-502, 2002.
[113] C. Bettstetter, G. Resta and P. Santi,“The node distribution of the random waypoint mobility model for wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.2, no.3, pp. 257-269, July-Sept. 2003.
[114] P. Santi,“The critical transmitting range for connectivity in mobile ad hoc networks,”IEEE Trans. on Mobile Computing, vol.4, no.3, pp. 310-317, May-June 2005.
[115] C. Bettstetter,“On the connectivity of ad hoc networks,”The Computer Journal, Special Issue on Mobile and Pervasive Computing, vol.47, no.4, pp. 432-447, Oxford University Press, July 2004.
[116] P. Lassila, E. Hyytia, H. Koskinen,“Connectivity properties of random waypoint mobility model for ad hoc networks,”in Proc. of the 4th Annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net 2005), France, June 2005.
[117] C. H. Foh, B. S. Lee,“A closed form network connectivity formula for one-dimensional MANETs,”IEEE ICC, Paris, France, pp. 3739-3742, June 2004.
[118] M. Desai and D. Manjunath,“On the connectivity in finite ad hoc networks,”IEEE Communications Letters, vol.6, no.10, pp.437-439, Oct. 2002.
[119] A. Ghasemi and S. Nader-Esfahani,“Exact probability of connectivity in one-dimensional ad hoc wireless networks,”IEEE Communication Letter, vol.10, no.4, pp.251-253, Apr. 2006.
[120] C. H. Foh, G. Liu, B. S. Lee, B. C. Seet, K.J. Wong and C.P. Fu,“Network connectivity of one-dimensional MANETs with random waypoint movement,”IEEE Communication Letter, vol.9, no.1, pp. 31-33, Jan., 2005.
[121] F. Kuhn, R. Wattenhofer, Y. Zhang, et al,“Geometric ad-hoc routing: of theory and practice,”in Proc. of the 22nd Annual Symposium on Principles of Distributed Computing, Boston, USA, July 2003, pp. 63-72.
[122] Y. J. Kim, R. Govindan, B. Karp, et al,“Geographic routing made practical,”in Proc. of the 2nd Symposium on Networked Systems Design and Implementation (NSDI), Boston, USA, May 2005, pp. 217-230.
[123] P. J. Wan, C. W. Yi,“On the longest edge of gabriel graphs in wireless ad hocnetworks,”IEEE Trans. on Parallel and Distributed Systems, vol.18, no.1, pp. 111-125, Jan. 2007.
[124] M. Sheng, J. D. Li, Y. Shi,“Critical nodes detection in mobile ad hoc network,”in Proc. of the 20th International Conference on Advanced Information Networking and Applications (IEEE AINA), Vienna, Austria, Apr. 2006, vol. 2, pp. 336-340.
[125] D. Goyal,“Partitioning avoidance in mobile ad hoc networks using network survivability concepts,”in Proc. of the 7th IEEE Symposium on Computers and Communications (ISCC), Taormina, Italy, July 2002, pp. 553-558.
[126] X. M. Liu, X. L. Xiao, A, Kreling, Y. H. Liu,“Optimizing overlay topology by reducing cut vertices,”in Proc. of the 2006 International Workshop on Network and operating systems support for digital audio and video(NOSSDAV,), Newport, Rhode Island, Nov. 2006, article no. 17.
[127] T. Q. Qiu, E. Chan, G. H. Chen,“Overlay partition: iterative detection and proactive recovery,”IEEE ICC, Glasgow, Scotland, June 2007, pp. 1854-1859.
[128] Z. Shen, Y. L. Chang, C. Cui, et al,“A fault-tolerant and minimum- energy path-preserving topology control algorithm for wireless multi-hop networks,”in Proc. of International Conference on Computational Intelligence and Security (CIS), Xi’an, China, Dec. 2005, pp. 864-869.
[129] D. Stephane,“A silent self-stabilizing algorithm for finding cut-nodes and bridges,”Parallel Processing Letters, vol.15, no.1~2, pp. 183– 198, Jan 2005.
[130] P. David,“An optimal distributed bridge-finding algorithm,”http://www.math. uwaterloo.ca/~dagpritc/math/2006/podc-bicon-poster.pdf, 2006.
[131] H. J. Kim,“Articulation points detection algorithm,”http://www.ibluemojo. com/school/articul_algorithm.html, 2006.
[132] M. Burkhart, V. R. Pascal, W. Roger, et al,“Does topology control reduce interference?,”ACM MobiHoc, Lausanne, Switzerland, June 2004, pp. 9-19.
[133] D. Perkins, E. McGinnis. Understanding SNMP MIBs. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1997.
[134] K. P. Eswaran, R. E. Tarjan,“Augmentation problems,”SIAM Jornal on Computing, vol.5, no.4, Apr. 1976, pp. 653-665.
[135] G. N. Frederckson, J. Jaja,“Approximation algorithms for several graph augmentation problems,”SIAM Jornal on Computing, vol.10, no.2, Feb. 1981, pp. 270-282.
[136] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci,“A survey on sensornetwork,”IEEE Communications Magazine, vol.40, no.8, Aug., 2002, pp. 102-105.
[137] C. Schurgers, G. Kulkarni, M. B. Srivastava,“Distributed on-demand address assignment in wireless sensor networks,”IEEE Trans. on Parallel and Distributed Systems, vol.13, no.10, Oct. 2002, pp. 1056-1065.
[138] D. Estrin, R. Govindan,“Next century challenges: scalable coordination in sensor networks,”ACM MobiCom, Seattle, UAS, Aug. 1999, pp. 263-270.
[139] J. Elson, D. Estrin,“Random, Ephemeral transaction identifiers in dynamic sensor networks,”in Proc. of the 21st International Conference on Distributed Computing Systems, Mesa, USA, Apr 2001, pp. 459-468.
[140] C. Schurgers, G. Kulkarni, M. B. Srivastava,“Distributed assignment of encoded MAC addresses in sensor networks,”ACM MobiHoc, Long Beach, USA, Oct. 2001, pp 295-298.
[141]谢希仁.计算机网络(第四版).电子工业出版社,北京, 2003.
[142] L. Loukas, P. Radha,“HiRLoc: High-resolution robust localization for wireless sensor networks,”IEEE Journal on Selected Areas in Communications, vol.24, no.2, pp. 233-246, Feb. 2006.
[143] R. Iyengar, B. Sikdar,“Scalable and distributed GPS free positioning for sensor networks,”IEEE ICC, Anchorage, USA, May 2003, pp. 338-342.
[144]江泽民.新时期我国信息技术产业的发展.上海交通大学学报, 2008, 42(10): 1608-1612.
[2]罗涛,乐光新.多天线无线通信原理与应用.北京邮电大学出版社,北京, 2005.
[3]杨家玮,盛敏,刘勤.移动通信基础.电子工业出版社,北京, 2008.
[4]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术.电子工业出版社,北京, 2006.
[5] http://www.cctime.com/html/2008-5-26/2008526924582280.htm, 2008
[6]张克平. LET-B3G/4G移动通信系统无线技术.电子工业出版社,北京, 2008.
[7]李建东,杨家玮.个人通信.人民邮电出版社,北京, 1998.
[8] D. C. Cox,“Wireless personal communication: what is it?,”IEEE Personal Communications, vol. 2, no. 2, pp. 20-35, Apr. 1995.
[9] M. S. Gast. 802.11无线网络权威指南(影印版).清华大学出版社,北京, 2002.
[10] http://www.hsdcw.com/HTML/2008-5-14/116704.HTM, 2008.
[11] http://www.sasac.gov.cn/n1180/n1226/n2410/n314349/4537213.html, 2008.
[12] http://www.cww.net.cn/news/html/2008/5/23/2008523750468663.htm, 2008.
[13]于宏毅等.无线移动自组织网.人民邮电出版社,北京, 2005.
[14] Ram Ramanathan and Jason Radi,“A brief overview of ad hoc network: challenges and directions,”IEEE Communication Magazine, 50th Anniversary Commemorative Issue, pp. 20-22, May 2002.
[15] B. Xu and S. Hischke,“The role of ad hoc networking in future wireless communications,”in Proc. of International Conference on Communication Technology Proceedings (ICCT), Beijing, China, Apr. 2003, pp. 1353-1358.
[16]孙立民,李建中,陈渝,朱红松.无线传感器网络.清华大学出版社,北京, 2005.
[17]李建中,李金宝,石胜飞.传感器网络及数据管理的概念、问题与进展.软件学报, 2003, 14(10): 1717-1727.
[18] J. Jubin, J. D. Tornow,“The DARPA packet radio network protocols,”in Proc. of IEEE Special Issue on Packet Radio Networks, vol.75, no.1, Jan., 1987, pp.21-32.
[19] D. A. Beyer,“Accomplishments of the DARPA SURAN Program,”in Proc. of IEEE Military Communication Conference (IEEE MILCOM), Monterey, USA, Sept. 1990, pp. 855-862.
[20] B. M. Leiner, R. J. Ruth, A. R. Sastry,“Goals and challenges of the DARPA GloMo Program,”IEEE Personal Communications, vol.3, no.6, pp.34-43, Dec. 1996.
[21]何非常,周吉,李振邦.军事通信——现代战争的神经网络.国防工业出版社,北京, 2000.
[22] http://www.ieee802.org/11/.
[23] http://www.ietf.cnri.reston.va.us/html.charters/manet-charter.html.
[24] J. P. Macker, M. S. Corson,“Mobile ad hoc networking and the IETF,”ACM SIGMOBILE Mobile Computing and Communications Review, vol. 2, no. 2, pp. 9-14, Apr. 1998.
[25] J. Macker, S. Corson , B. Fenner, et al,“Mobile ad hoc networks,”http//www. ietf.Org/html.Charters/manet-charter.html.
[26] A. B. McDonald and T. F. Znati,“A mobility-based framework for adaptive clustering in wireless ad hoc networks,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp. 1466-1487, Aug. 1999.
[27] H. Q. Zhai, J. F. Wang, X. Chen, Y. G. Fang,“Medium access control in mobile ad hoc networks: challenges and solutions,”Wireless communications and Mobile Computing, vol. 6, no.2, pp. 151-170, Feb. 2006.
[28] E. S. Jung and N. H. Vaidya,“A power control MAC protocol for ad hoc networks,”Wireless Networks, vol.11, no.1-2, pp. 55-66, Jan. 2005.
[29] M. Mauve, A. Widmer, H. Hartenstein,“A survey on position-based routing in mobile ad hoc networks,”IEEE Network, vol.15, no.6, pp.30-39, Nov. 2001.
[30] R. Rajaraman,“Topology control and routing in ad hoc networks: a survey,”ACM SIGACT News, vol.33, no.2, pp. 60-73, June 2002.
[31]臧婉瑜,于勐,谢立,孙钟秀.按需式ad hoc移动网络路由协议的研究进展.计算机学报, 2002, 25(10): 1009-1017.
[32] A. Ahuja, S. Agarwal, J. P. Singh, R. Shorey,“Performance of TCP over different routing protocols in mobile ad hoc networks,”IEEE VTC-Spring, Tokyo, Japan, May 2000, pp. 2315-2319.
[33] W. Chen, N. Jain, S. Singh,“ANMP: ad hoc network management protocol,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp. 1506-1531, Aug. 1999.
[34]李云,赵为粮,隆克平,吴诗其.无线Ad Hoc网络支持QoS的研究进展与展望.软件学报, 2004, 15(12): 1885-1893.
[35] P. McDermott-Wells,“What is Bluetooth?,”IEEE Potentials, vol.23, no.5, pp. 33-35, Dec. 2004.
[36] D. Chen, S. Garg and K. S. Trivedi,“Network survivability performance evaluation: a quantitative approach with applications in wireless ad hoc networks,”in Proc. of MSWiM’02, Atlanta, USA, Spet. 2002, pp. 61-68.
[37] J. P. G. Sterbenz, R. Krishnan, et al,“Survivable mobile wireless networks: issues, challenges, and research directions,”in Proc. of the 1st ACM workshop on Wireless Security, Atlanta, USA, Sept. 2002, pp. 31-40.
[38] N. Li and J. C. Hou,“Topology control in heterogeneous wireless networks: problems and solutions,”IEEE INFOCOM, Hong Kong, China, Mar. 2004, pp. 232-242.
[39] I. Stojmenovic, M. Seddigh and J. Zunic,“Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks,”IEEE Trans. on Parallel and Distributed Systems, vol.13, no.1, pp. 14-25, Jan. 2002.
[40] S. Toumpis, A. Goldsmith,“Ad hoc network capacity,”in Proc. of the 34th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, Aug. 2000, pp. 1265-1269.
[41] P. Gupta, P. R. Kumar,“The capacity of wireless networks,”IEEE Trans. on Information Theory, vol.46, no.2, pp. 388-404, Mar. 2000.
[42] M. Cardei, J. Wu, S. Yang,“Topology control in ad hoc wireless networks using cooperative communication,”IEEE Trans. on Mobile Computing, vol.5, no.6, pp. 711-724, June 2006.
[43] V. Strvastava, M. Motani,“Cross-layer design: a survey and the road ahead,”IEEE Communications Magazine, vol.43, no.12, pp. 112-119, Dec. 2005.
[44] J. Gomez and A. T. Campbell,“Variable-range transmission power control in wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.6, no.1, pp. 87-99, Jan. 2007.
[45] P. Bose, P. Morin, I. Stojmenovic, J. Urrutia,“Routing with guaranteed delivery in ad hoc wireless networks,”Wireless Networks, vol.7, no.6, pp. 609-616, Nov. 2001.
[46] I. Stojmenovic,“Position-based routing in ad hoc networks,”IEEE Communications Magazine, vol.40, no.7, pp. 128-134, Jul. 2002.
[47] Paolo Santi. Topology Control in Wireless Ad Hoc and Sensor Networks. JohnWiley & Sons Ltd, England, 2005.
[48] Paolo Santi,“Topology control in wireless ad hoc and sensor networks,”ACM Computing Surveys, vol.37, no.2, pp.164-194, June 2005.
[49] A. A. Jeng and R. H. Jan,“An adaptive topology control scheme for energy-efficient routing in mobile ad hoc networks,”IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 4404-4407.
[50] L. Li and J. Y. Halpern,“A minimum-energy path-preserving topology-control algorithm,”IEEE Trans. on Wireless Communications, vol.3, no.3, pp.910-921, May 2004.
[51] A. Rahman, P. Gburzynski,“On constructing minimum-energy path-preserving graphs for ad-hoc wireless networks,”IEEE ICC, Seoul, Korea, May 2005, pp. 3083-3087.
[52] R. Basu and J. Redi,“Movement control algorithms for realization of fault-tolerant ad hoc robot networks,”IEEE Network, vol.18, no.4, pp.36-44, July-Aug. 2004.
[53] Z. Huang and C. Shen et al,“Topology control for ad hoc networks with directional antennas,”in Proc. of IEEE International Conference on Communication and Networks (ICCCN), Miami, USA, Oct. 2002, pp. 16-21.
[54] D. B. West. Introduction to Graph Theory, Second Edition. China Machine Press, Beijing, 2004.
[55] L. Kirousis, E. Kranakis, D. Krizanc, A. Pelc,“Power consumption in packet radio networks,”Theoretical Computer Science, vol.243, no.1-2, pp. 289-305, July 2000.
[56] A. Clementi, P. Penna, R. Silvestri,“Hardness results for the power range assignment problem in packet radio networks,”Lecture Notes in Computer Science, vol. 1671, pp. 197-208, 2004.
[57] T. H. Cormen, C. E. Leiserson, R. L. Rivest, et al. Introduction to Algorithms, Second Edition. Higher Education Press, Beijing, 2002.
[58] R. Ramanathan and R. Roasles-Hain,“Topology control of multihop wireless networks using transmit power adjustment,”IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000, pp.404-413.
[59] E. L. Lloyd, R. Liu, M. V. Marathe, et al,“Algorithmic aspects of topology control problems for ad hoc networks,”ACM Mobihoc, Lausanne, Switzerland, June 2002, pp. 123-134.
[60] G. Y. Pei, M. Gerla, X. Y. Hong,“LANMAR: landmark routing for large scale wireless ad hoc networks with group mobility,”in Proc. of the 1st ACM international symposium on Mobile ad hoc networking & computing, Boston, USA, 2000, pp. 11-18.
[61] X. Y. Li, P. J. Wan and Y. Wang,“Power efficient and sparse spanner for wireless ad hoc networks,”in Proc. of the 10th International Conference on Computer Communications and Networks, Scottsdale, USA, Oct. 2001, pp. 564-567.
[62] A. A. Jeng and R. H. Jan,“The r-neighborhood graph: an adjustable structure for topology control in wireless ad hoc networks,”IEEE Trans. on Parallel and Distributed Systems, vol.18, no.4, pp. 536-549, April, 2007.
[63] Brad K, Kung H T,“GPSR: greedy perimeter stateless routing for wireless networks,”ACM MOBICOM, Boston, USA, Aug. 2000, pp.243-254.
[64] V. Rodoplu and T. H. Meng,“Minimum energy mobile wireless networks,”IEEE Journal on Selected Areas in Communications, vol.17, no.8, pp.1333-1344, Aug. 1999.
[65] L. Li and J. Y. Halpern,“Minimum-energy mobile wireless networks revisited,”IEEE ICC, St. Petersburg, Russia, Jun. 2001, pp. 278-283.
[66] N. Li, J. Hou and L. Sha,“Design and analysis of an MST-based topology control algorithm,”IEEE Trans. on Wireless Communications, vol.4, no.3, pp. 1195-1206, May 2005.
[67] N. Li and J. Hou,“Localized fault-tolerant topology control in wireless ad hoc networks,”IEEE Trans. on Parallel and Distributed Systems, vol.17, no.4, pp. 307-320, April 2006.
[68] L. Li, J. Y. Halpern, P. Bahl, Y. Wang and R. Wattenhofer,“A cone-based distributed topology-control algorithm for wireless multi-hop networks,”IEEE/ACM Trans. on Networking, vol.13, no.1, pp. 147-159, Feb. 2005.
[69] M. Bahramgiri, M. Hajiaghayi and V. Mirrokni,“Fault-tolerant and 3-dimensional distrbuted topology control algorithms in wireless multi-hop networks,”in Proc. of International Conference on Communication and Networks (ICCCN), Miami, USA, Oct. 2002, pp.392-397.
[70] R. Wattenhofer and A. Zollinger,“XTC: a practical topology control for ad hoc networks,”in Proc. of 18th Parallel and Distributed Processing Symposium, Santa Fe, USA, Apr. 2004, pp.26-30.
[71]路纲,周明天,牛新征,佘堃,唐勇,秦科.无线网络邻近图综述.软件学报, 2008, 19(4): 888-911.
[72] G.. T. Toussaint,“The relative neighborhood grap of a finite planar set,”Pattern Recognition, vol.12, no. 4, pp. 261.268, 1980.
[73] K. R. Gabriel and R. R. Sokal,“A new statistical approach to geographic variation analysis,”Systematic Zoology, vol.18, pp.259-278, 1969.
[74] J. Geo, L. J. Guibas, J. Hershburger, L. Zhang and A. Zhu,“Geometric spanners for routing in mobile networks,”IEEE Journal on Selected Areas in Communications, vol.23, no.1, pp. 174-185, Jan. 2005.
[75] X. Y. Li, G. Calinescu, P. J. Wan and Y. Wang,“Localized delaunay triangulation with application in ad hoc wireless networks,”IEEE Trans. on Parallel and Distributed Systems, vol.14, no.10, pp. 1035-1047, Oct. 2003.
[76] A. C. C. Yao,“On constructing minimum spanning trees in k-dimensional spaces and related problems,”SIAM J. Computing, vol. 11, pp. 721-736, 1982.
[77] Y. Wang, X. Li and O. Frieder,“Distributed spanners with bounded degree for wireless ad hoc networks,”International Journal of Foundations of Computer Science, vol.14, no.2, pp. 183-200, 2002.
[78] W. Song, Y. Wang, X. Li and O. Frieder,“Localized algorithms for energy efficient topology in wireless ad hoc networks,”ACM MobiHoc, Tokyo, Japan, May 2004, pp. 98-108.
[79] C. E. Jones, K. M. Sivalingam, P. Agrawal and J. C. Chen,“A survey of energy efficient network protocols for wireless networks,”Wireless Networks, vol. 7, no.4, pp. 343-358, Aug. 2001.
[80] L. Li, J. Y. Halpern, P. Bahl, Y. M. Wang and R. Wattenhofer,“Analysis of a cone-based distributed topology control algorithm for wireless multihop networks,”in Proc. of ACM Symposium on Principles of Distributed Computing (PODC), Newport, USA, Aug. 2001, pp. 264-273.
[81] D. Blough, M. Leoncini, G. Resta and P. Santi,“The k-neighbors protocol for symmetric topology control in ad hoc networks,”in Proc. of ACM MobiHoc, Annapolis, USA, June 2003, pp. 141-152.
[82] Y. Shen, Y. Cai and X. M. Xu,“A shortest-path-based topology control algorithm in wireless multihop networks,”ACM SIGCOMM Computer Communication Review, vol. 37, no. 5, pp. 29-38, Oct. 2007.
[83] E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi,“Algorithmic aspects of topology control problems for ad hoc networks,”Mobile Networks and Applications, vol. 10, no. 1-2, pp. 19-34, Feb. 2005.
[84] Y. Cui, Y. Xue and K, Nahrstedt,“A utility-based distributed maximum lifetime routing algorithm for wireless networks,”IEEE Trans. Vehicular Technology, vol. 55, no.3, pp. 797-805, May 2006.
[85] H. Wang, Y. Yang and M. Ma,“Network lifetime global optimization by duality approach in wireless sensor networks,”IEEE GLOBECOM, Washington, DC, USA, Nov. 2007, pp. 1017-1021.
[86] A. Sankar, Z. Liu,“Maximum lifetime routing in wireless ad-hoc networks,”IEEE INFOCOM, Hong Kong, China, Mar. 2004, pp. 1089-1097.
[87] R. Zhang, M. A. Labrador,“Energy-aware topology control in heterogeneous wireless multi-hop networks,”in Proc. of the 2nd International Symposium on Wireless Pervasive Computing (ISWPC), San Juan, Puerto Rico, Feb. 2007, pp. 25-30.
[88] B. X. Zhang, Z. Zhao, J. Ma and H. T. Mouftah,“Efficient localized topology control algorithm,”in Proc. of International workshop on High Performance Switching and Routing (HPSR), New York, USA, June 2007, pp. 1-6.
[89] J. P. Sheu, S. C. Tu and C. H. Hsu,“Location-free topology control protocol in wireless ad hoc networks,”IEEE WCNC, Hong Kong, China, Mar. 2007, pp. 66-71.
[90] R. S. Rappaport. Wireless Communications: Principles and Practice, Second Edition. Publishing House of Electronics Industry, Beijing, 2004.
[91] S. H. Lee, J. M. Choi and Y. B. Ko,“UAMAC: Unidirectional-link aware MAC protocol for heterogeneous ad hoc networks,”Ad-Hoc, Mobile, and Wireless Networks, vol. 3158, pp. 336-341, 2004.
[92] V. Ramasubramanian, D. Mosse,“BRA: A bidirectional routing abstraction for asymmetric mobile ad hoc networks,”IEEE/ACM Trans. Networking, vol. 16, no.1, pp. 116-129, Feb. 2008.
[93] J. L. Liu, B. C. Li,“Distributed topology control in wireless sensor networks with asymmetric links,”IEEE GLOBECOM, San Francisco, USA, Dec. 2003, pp. 1257-1262.
[94] http://en.wikipedia.org/wiki/Dijkstra's_algorithm.
[95] J. H. Chang, L. Tassiulas,“Maximum life routing in wireless sensor networks,”IEEE/ACM Trans. Networking, vol.12, no.4, pp. 609-619, Aug. 2004.
[96] X. J. Du, D. Wu, W. Liu and Y. G. Fang,“Multiclass routing and medium access control for heterogeneous mobile ad hoc networks,”IEEE Trans. Vehicular Technology, vol. 55, no.1, pp. 270-277, Jan. 2006.
[97] N. Li, J. and C. Hou,“Localized topology control algorithms for heterogeneouswireless networks,”IEEE/ACM Trans. Networking, vol.13, no.6, pp. 1313-1324, Dec. 2005.
[98] J. L. Liu, B. C. Li,“Distributed topology control in wireless sensor networks with asymmetric links,”IEEE GLOBECOM, San Francisco, USA, Dec. 2003, pp. 1257-1262.
[99] M. Penrose. Random Geometric Graphs. Oxford University Press, Oxford, 2003.
[100] M. Penrose,“The longest edge of the random minimal spanning tree,”The Annals of Applied Probability, vol.7, no.2, pp.340-361, 1997.
[101] M. Penrose,“Extremes for the minimal spanning tree on normally distributed points,”Advances in Applied Probability, vol.30, no.3, pp.628-639, 1998.
[102] M. Penrose,“On k-connectivity for a geometric random graph,”Random Structures and Algorithms, vol.15, no.2, pp.145-164, 1999.
[103] M. Penrose,“A strong law for the largest nearest–neighbour link between random points,”Journal of London Mathematical Society, vol.60, no.2, pp.951-960, 1999.
[104] M. Penrose,“A strong law for the largest edge of the minimal spanning tree,”The Annals of Probability, vol.27, no.1, pp.246-260, 1999.
[105] L. Holst,“On multiple covering of a circle with random arcs,”Journal of Applied Probability, vol.16, pp. 284-290, 1980.
[106] H. Dette, N. Henze,“The limit distribution of the largest nearest neighbor link in the unit d-cube,”Journal of Applied Probability, vol.26, pp. 67-80, 1989.
[107] P. Wan, C. Yi,“Asymptotical critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks,”ACM MobiHoc, Tokyo, Japan, May 2004, pp. 1-8.
[108] P. Santi and D. M. Blough,“The critical transmitting range for connectivity in sparse wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.2, no.1, pp. 25-39, 2003.
[109] P. Santi, D. M. Blough and F. Vainstein,“A probabilistic analysis for the range assignment problem in ad hoc networks,”ACM MobiHoc, Long Beach, USA, Oct. 2001, pp. 212-220.
[110] C. Bettstetter,“On the minimum node degree and connectivity of a wireless multihop network,”ACM MobiHoc, Lausanne, Switzerland, June 2002, pp.80-91.
[111] C. Bettstetter,“On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment,”IEEE VTC, Birmingham, USA,May 2002, pp.1706-1710.
[112] T. Camp, J. Boleng and V. Davies,“A survey of mobility for ad hoc network research,”Wireless Communication & Mobile Computing (WCMC), Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol.2, no.5, pp. 483-502, 2002.
[113] C. Bettstetter, G. Resta and P. Santi,“The node distribution of the random waypoint mobility model for wireless ad hoc networks,”IEEE Trans. on Mobile Computing, vol.2, no.3, pp. 257-269, July-Sept. 2003.
[114] P. Santi,“The critical transmitting range for connectivity in mobile ad hoc networks,”IEEE Trans. on Mobile Computing, vol.4, no.3, pp. 310-317, May-June 2005.
[115] C. Bettstetter,“On the connectivity of ad hoc networks,”The Computer Journal, Special Issue on Mobile and Pervasive Computing, vol.47, no.4, pp. 432-447, Oxford University Press, July 2004.
[116] P. Lassila, E. Hyytia, H. Koskinen,“Connectivity properties of random waypoint mobility model for ad hoc networks,”in Proc. of the 4th Annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net 2005), France, June 2005.
[117] C. H. Foh, B. S. Lee,“A closed form network connectivity formula for one-dimensional MANETs,”IEEE ICC, Paris, France, pp. 3739-3742, June 2004.
[118] M. Desai and D. Manjunath,“On the connectivity in finite ad hoc networks,”IEEE Communications Letters, vol.6, no.10, pp.437-439, Oct. 2002.
[119] A. Ghasemi and S. Nader-Esfahani,“Exact probability of connectivity in one-dimensional ad hoc wireless networks,”IEEE Communication Letter, vol.10, no.4, pp.251-253, Apr. 2006.
[120] C. H. Foh, G. Liu, B. S. Lee, B. C. Seet, K.J. Wong and C.P. Fu,“Network connectivity of one-dimensional MANETs with random waypoint movement,”IEEE Communication Letter, vol.9, no.1, pp. 31-33, Jan., 2005.
[121] F. Kuhn, R. Wattenhofer, Y. Zhang, et al,“Geometric ad-hoc routing: of theory and practice,”in Proc. of the 22nd Annual Symposium on Principles of Distributed Computing, Boston, USA, July 2003, pp. 63-72.
[122] Y. J. Kim, R. Govindan, B. Karp, et al,“Geographic routing made practical,”in Proc. of the 2nd Symposium on Networked Systems Design and Implementation (NSDI), Boston, USA, May 2005, pp. 217-230.
[123] P. J. Wan, C. W. Yi,“On the longest edge of gabriel graphs in wireless ad hocnetworks,”IEEE Trans. on Parallel and Distributed Systems, vol.18, no.1, pp. 111-125, Jan. 2007.
[124] M. Sheng, J. D. Li, Y. Shi,“Critical nodes detection in mobile ad hoc network,”in Proc. of the 20th International Conference on Advanced Information Networking and Applications (IEEE AINA), Vienna, Austria, Apr. 2006, vol. 2, pp. 336-340.
[125] D. Goyal,“Partitioning avoidance in mobile ad hoc networks using network survivability concepts,”in Proc. of the 7th IEEE Symposium on Computers and Communications (ISCC), Taormina, Italy, July 2002, pp. 553-558.
[126] X. M. Liu, X. L. Xiao, A, Kreling, Y. H. Liu,“Optimizing overlay topology by reducing cut vertices,”in Proc. of the 2006 International Workshop on Network and operating systems support for digital audio and video(NOSSDAV,), Newport, Rhode Island, Nov. 2006, article no. 17.
[127] T. Q. Qiu, E. Chan, G. H. Chen,“Overlay partition: iterative detection and proactive recovery,”IEEE ICC, Glasgow, Scotland, June 2007, pp. 1854-1859.
[128] Z. Shen, Y. L. Chang, C. Cui, et al,“A fault-tolerant and minimum- energy path-preserving topology control algorithm for wireless multi-hop networks,”in Proc. of International Conference on Computational Intelligence and Security (CIS), Xi’an, China, Dec. 2005, pp. 864-869.
[129] D. Stephane,“A silent self-stabilizing algorithm for finding cut-nodes and bridges,”Parallel Processing Letters, vol.15, no.1~2, pp. 183– 198, Jan 2005.
[130] P. David,“An optimal distributed bridge-finding algorithm,”http://www.math. uwaterloo.ca/~dagpritc/math/2006/podc-bicon-poster.pdf, 2006.
[131] H. J. Kim,“Articulation points detection algorithm,”http://www.ibluemojo. com/school/articul_algorithm.html, 2006.
[132] M. Burkhart, V. R. Pascal, W. Roger, et al,“Does topology control reduce interference?,”ACM MobiHoc, Lausanne, Switzerland, June 2004, pp. 9-19.
[133] D. Perkins, E. McGinnis. Understanding SNMP MIBs. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1997.
[134] K. P. Eswaran, R. E. Tarjan,“Augmentation problems,”SIAM Jornal on Computing, vol.5, no.4, Apr. 1976, pp. 653-665.
[135] G. N. Frederckson, J. Jaja,“Approximation algorithms for several graph augmentation problems,”SIAM Jornal on Computing, vol.10, no.2, Feb. 1981, pp. 270-282.
[136] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci,“A survey on sensornetwork,”IEEE Communications Magazine, vol.40, no.8, Aug., 2002, pp. 102-105.
[137] C. Schurgers, G. Kulkarni, M. B. Srivastava,“Distributed on-demand address assignment in wireless sensor networks,”IEEE Trans. on Parallel and Distributed Systems, vol.13, no.10, Oct. 2002, pp. 1056-1065.
[138] D. Estrin, R. Govindan,“Next century challenges: scalable coordination in sensor networks,”ACM MobiCom, Seattle, UAS, Aug. 1999, pp. 263-270.
[139] J. Elson, D. Estrin,“Random, Ephemeral transaction identifiers in dynamic sensor networks,”in Proc. of the 21st International Conference on Distributed Computing Systems, Mesa, USA, Apr 2001, pp. 459-468.
[140] C. Schurgers, G. Kulkarni, M. B. Srivastava,“Distributed assignment of encoded MAC addresses in sensor networks,”ACM MobiHoc, Long Beach, USA, Oct. 2001, pp 295-298.
[141]谢希仁.计算机网络(第四版).电子工业出版社,北京, 2003.
[142] L. Loukas, P. Radha,“HiRLoc: High-resolution robust localization for wireless sensor networks,”IEEE Journal on Selected Areas in Communications, vol.24, no.2, pp. 233-246, Feb. 2006.
[143] R. Iyengar, B. Sikdar,“Scalable and distributed GPS free positioning for sensor networks,”IEEE ICC, Anchorage, USA, May 2003, pp. 338-342.
[144]江泽民.新时期我国信息技术产业的发展.上海交通大学学报, 2008, 42(10): 1608-1612.