无线自组织网络拓扑结构研究
|
摘要
普适计算系统将信息的采集、传输、处理、使用融为和谐一体，为我们展示了未来信息社会的美好图景。
无线网络是即将到来的普适计算时代的一个基本组成模块，本文研究了无线自组织网络拓扑结构中的一些关键问题，包括：连通支配集问题、节点定位、不同类型路由协议及拓扑结构下无线传感器网络的寿命分析、拓扑结构的可信计算。
论文主要内容如下：
(1)详细综述了前人在无线自组织网络拓扑图结构方面的相关工作，并证明了YG平均边长表达式和UDG连通性表达式，研究了图结构之间的拓扑关系，给出了一些重要拓扑参数的仿真结果。
(2)以几何信息作为启发策略，设计了UDG中连通支配集问题的分布式、中心式近似算法。仿真结果显示，本文算法优于目前已知的一些算法。(3)定义了完全Voronoi图和镜像分布，证明了镜像分布的概率密度，从而解释了完全Voronoi图的中心效应。还证明了下列表达式：基于完全Voronoi图的定位算法的平均定位误差表达式，完全Voronoi图中的点、边、面间数量关系表达式，平均弦长表达式，归属多边形的平均边数表达式。提出了民意投票技术Polling，并在数学上表明了其工作原理。这种技术可提高完全Voronoi图定位算法的定位精度，就我们所知，这是首个利用未知节点提高系统定位精度的技术。仿真研究了当测量信号强度存在误差时，算法的误差性能。
(4)给出了不同类型路由协议和拓扑结构下，无线传感器网络的寿命模型。利用这个模型，可以定量计算网络中任意位置的平均能耗率，进而预测网络的平均寿命。
(5)提出了一种处理舍入误差的ε分析技术，研究了退化问题处理方法。使用文中方法，可以有效提高Voronoi图算法实施的健壮性、保证计算结果的正确性。
The pervasive computing system, which integrates the collection, transmission, processing and utilization of information into a harmonious whole, shows us a prosperous vision for a bright future of information society.
Wireless network is one of the fundamental building blocks of the forthcoming century of pervasive computing. In this dissertation, we investigated some key research issues about the topology of wireless ad-hoc networks including the connected dominating set problem, localization of the nodes, lifetime analysis of WSNs under different routing protocols and topologies, and the trusted computing for the network topology.
The main results of this dissertation are as follows:
(1) A detailed survey of the previous research works on the topology of wireless ad hoc networks is given in this dissertation. In the survey mentioned above, we proved the expressions of the average length of edges in YG and the connectivity of UDG, respectively. The topology relationships between different graphs are studied and the simulation results of some important parameters are obtained.
(2) Using some geometric information as the heuristics, several distributed and centralized approximation algorithms for the CDS problem in UDGs are proposed in this dissertation. The simulation results show that our algorithms perform better than some known ones.
(3) The conceptions of the Complete Voronoi Diagram (CVD) and the Mirror Image distribution are defined respectively, and the center effect of the CVD is interpreted through the proving of the expression of the probability density function of the mirror image distribution. The following expressions have also been proved: the expresson of the average localization errors of the CVD based algorithms; the expression for the relationship between the number of vertices, edges and faces in CVD; the expression of the average length of chords in CVD; and the expression for the average number of edges of an attached pologon in CVD. The Polling technique which, to our knowledge, is the first technique that can make use of the information provided by unknown nodes to help us improve the error performance of the CVD based localization algorithms has been proposed, and the mathematical interpretation for the principle of the Polling has been presented. The error performance of the localization scheme in presence of signal strength measurement erros is investigated through simulations.
(4) Lifetime model for the wireless sensor networks (WSNs) under different routing protocls and topologies has been proposed. Using this model we can calculate the average energy dissipation ratio of anywhere in the network region and predict the average lifetime of WSNs.
(5) Aε-anslysis technique for handling the round off errors and the methods to deal with the degeneration cases are proposed. The methodologies mentioned in this dissertation can help us efficiently improve the robustness of the implementation of the Voronoi diagram construction algorithms and ensure the correctness of the computation results.
无线网络是即将到来的普适计算时代的一个基本组成模块，本文研究了无线自组织网络拓扑结构中的一些关键问题，包括：连通支配集问题、节点定位、不同类型路由协议及拓扑结构下无线传感器网络的寿命分析、拓扑结构的可信计算。
论文主要内容如下：
(1)详细综述了前人在无线自组织网络拓扑图结构方面的相关工作，并证明了YG平均边长表达式和UDG连通性表达式，研究了图结构之间的拓扑关系，给出了一些重要拓扑参数的仿真结果。
(2)以几何信息作为启发策略，设计了UDG中连通支配集问题的分布式、中心式近似算法。仿真结果显示，本文算法优于目前已知的一些算法。(3)定义了完全Voronoi图和镜像分布，证明了镜像分布的概率密度，从而解释了完全Voronoi图的中心效应。还证明了下列表达式：基于完全Voronoi图的定位算法的平均定位误差表达式，完全Voronoi图中的点、边、面间数量关系表达式，平均弦长表达式，归属多边形的平均边数表达式。提出了民意投票技术Polling，并在数学上表明了其工作原理。这种技术可提高完全Voronoi图定位算法的定位精度，就我们所知，这是首个利用未知节点提高系统定位精度的技术。仿真研究了当测量信号强度存在误差时，算法的误差性能。
(4)给出了不同类型路由协议和拓扑结构下，无线传感器网络的寿命模型。利用这个模型，可以定量计算网络中任意位置的平均能耗率，进而预测网络的平均寿命。
(5)提出了一种处理舍入误差的ε分析技术，研究了退化问题处理方法。使用文中方法，可以有效提高Voronoi图算法实施的健壮性、保证计算结果的正确性。
The pervasive computing system, which integrates the collection, transmission, processing and utilization of information into a harmonious whole, shows us a prosperous vision for a bright future of information society.
Wireless network is one of the fundamental building blocks of the forthcoming century of pervasive computing. In this dissertation, we investigated some key research issues about the topology of wireless ad-hoc networks including the connected dominating set problem, localization of the nodes, lifetime analysis of WSNs under different routing protocols and topologies, and the trusted computing for the network topology.
The main results of this dissertation are as follows:
(1) A detailed survey of the previous research works on the topology of wireless ad hoc networks is given in this dissertation. In the survey mentioned above, we proved the expressions of the average length of edges in YG and the connectivity of UDG, respectively. The topology relationships between different graphs are studied and the simulation results of some important parameters are obtained.
(2) Using some geometric information as the heuristics, several distributed and centralized approximation algorithms for the CDS problem in UDGs are proposed in this dissertation. The simulation results show that our algorithms perform better than some known ones.
(3) The conceptions of the Complete Voronoi Diagram (CVD) and the Mirror Image distribution are defined respectively, and the center effect of the CVD is interpreted through the proving of the expression of the probability density function of the mirror image distribution. The following expressions have also been proved: the expresson of the average localization errors of the CVD based algorithms; the expression for the relationship between the number of vertices, edges and faces in CVD; the expression of the average length of chords in CVD; and the expression for the average number of edges of an attached pologon in CVD. The Polling technique which, to our knowledge, is the first technique that can make use of the information provided by unknown nodes to help us improve the error performance of the CVD based localization algorithms has been proposed, and the mathematical interpretation for the principle of the Polling has been presented. The error performance of the localization scheme in presence of signal strength measurement erros is investigated through simulations.
(4) Lifetime model for the wireless sensor networks (WSNs) under different routing protocls and topologies has been proposed. Using this model we can calculate the average energy dissipation ratio of anywhere in the network region and predict the average lifetime of WSNs.
(5) Aε-anslysis technique for handling the round off errors and the methods to deal with the degeneration cases are proposed. The methodologies mentioned in this dissertation can help us efficiently improve the robustness of the implementation of the Voronoi diagram construction algorithms and ensure the correctness of the computation results.
引文
[1]M．Weiser．The Computer for the 21st century．Scientific American， 1991， 265(3)：94-104
[2]H．Breu， D．G．Kirkpatrick．Unit disk graph recognition is NP-hard．Computational Geometry Theory and Applications， 1998， 9 (1-2)： 3-24
[3]F．P．Preparata and M．I．Shamos．Computational geometry-an introduction．New York：Springer-Verlag， 1985， 1-205
[4]A．C．Yao．On constructing minimum spanning trees in k-dimensional spaces and related problems．SIAM Journal Computing， 1982，11(4)：721-736
[5]M．D．Penrose．The longest edge of the random minimal spanning tree．The Annals of Applied Probability， 1997， 7(2)：340-361
[6]E．N．Gilbert， H．O．Pollak．Steiner minimal trees．SIAM Journal on Applied Mathematics， 1968， 16(1)：1-29
[7]D．Z．Du， F．K．Hwang．A proof of gilbert-pollack's conjecture on the steiner ratio．Algorithmica， 1992， 7：121-135
[8]R．M．Karp．Reducibility among combinatorial problems．In： R．E．Miller， J．W．Thatcher， eds．Proc．of the Complexity of Computer Computations， New York： Plenum Press， 1972， 85-103
[9]M．R．Garey， R．L．Graham， D．S．Johnson．The complexity of computing Steiner minimal trees．SIAM Journal on Applied Mathematics， 1977， 32(4)：835-859
[10]N．Meghanathan．Determining a sequence of stable multicast Steiner trees in mobile ad hoc networks．In： Menezes R， ed．ACM Proc．of the 44th Annual Southeast Regional Conf．New York： ACM Press， 2006， 102-106
[11]A．A．-K Jeng， 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， 2007，18(4)：536-549
[12]P．Bose， L．Devroye， W．Evans， D．Kirkpatrick．On the spanning ratio of gabriel graphs and beta-skeletons．In： Rajsbaum S， ed．Proc．of the Latin．Theoretical Informatics Conf．Berlin：Springer-Verlag， 2002，479-493
[13]K．J．Supowit．The relative neighborhood graph， with an application to minimum spanning trees．Journal of Association for Computing Machinery， 1983， 30(3)：428-448
[14]G．T．Toussaint．The relative neighborhood graph of a finite planar set．Pattern Recognition，1980， 12(4)：261-268
[15]K．R．Gabriel， R．R．Sokal．A new statistical approach to geographic variation analysis．Systematic Zoology， 1969， 18(3)：259-278
[16]X．Y．Li， P．J．Wan， Y．Wang， O．Frieder．Sparse power efficient topology for wireless networks．In： Sprague RH， Jr．， eds．Proc．of the 35th Annual Hawaii Intl Conf on System Sciences．Washington： IEEE Computer Society， 2002， 296-306
[17]P．J．Wan， C．W．Y．On the longest edge of gabriel graphs in wireless ad hoc networks．IEEE Trans．on Parallel and Distributed Systems， 2007， 18(1)：111-125
[18]X．Y．Li， G．Calinescu， P．J．Wan， Y．Wang．Localized delaunay triangulation with application in ad hoc wireless networks．IEEE Trans．on Parallel and Distributed Systems， 2003，14(10)：1035-1047
[19]X．Y．Li， G．Calinescu， P．J．Wan．Distributed construction of planar spanner and routing for ad hoc wireless networks．In： Kermani P， Lee D， Orda A， eds．Proc．of the 21st Annual Joint Conf of the IEEE Computer and Communications Societies．Washington：IEEE Computer Society， 2002， 1268-1277
[20]P．Santi．Topology control in wireless ad hoc and sensor networks．ACM Computing Surveys， 2005， 37(2)：164-194
[21]S．Ruhrup， C．Schindelhauer， K．Volbert， M．Grunewald．Performance of distributed algorithms for topology control in wireless networks．In： Werner B， ed．Proc．of the IEEE Parallel and Distributed Processing Symp．Dublin： Broadcom Eireann Res．Ltd．， 2003，582-590
[22]R．Wattenhofer， L．Li， P．Bahl， Y．M．Wang．Distributed topology control for power efficient operation in multihop wireless ad hoc networks．In： Sengupta B， Kermani P， Lee D， eds．Proc of the 20th Annual Joint Conf．of the IEEE Computer and Communications Societies．Washington： IEEE Computer Society， 2001， 1388-1397
[23]L．Li， J．Y．Halpern， P．Bahl， et al．．Analysis of a cone-based distributed topology control algorithm for wireless multihop networks．In： Kshemkalyani A， Shavit N， eds．ACM Proc．of the 20th Annual Symp．on Principles of Distributed Computing．New York： ACM Press，2001， 264-273
[24]N．Li， J．C．Hou， S．Lui．Design and analysis of an mst-based topology control algorithm．IEEE Trans．on Wireless Communications， 2005， 4(3)：1195-1206
[25]V．Rodoplu， T．H．Meng．Minimum energy mobile wireless networks．IEEE J．Sel．Areas Communication， 1999， 17(8)：1333-1344
[26]L．Li， J．Y．Halpern．Minimum-Energy mobile wireless networks revisited．Communications．In： Shahin MK， ed．Proc．of the IEEE Int'l Conf．on Communacations (ICC 2001)．Washington： IEEE Computer Society， 2001， 278-283
[27]D．England， B．Veeravalli， J．B．Weissman．A robust spanning tree topology for data collection and dissemination in distributed environments．IEEE Trans．on Parallel and Distributed Systems， 2007， 18(5)：608-620
[28]M．Burkhart， P．von Rickenbach， R．Wattenhofer， et al．．Does topology control reduce interference? In： Murai J， Perkins C， Tassiulas L， eds．Proc．of the 5th ACM Int'1 Symp．on Mobile Ad Hoc Networking and Computing．New York： ACM Press， 2004， 9-19
[29]N．Li， J．C．Hou．Localized fault-tolerant topology control in wireless ad hoc networks．IEEE Trans．on Parallel and Distributed Systems， 2006， 17(4)：307-320
[30]M．D．Penrose．On K-connecitivity for a geometric random graph．Random Structures and Algorithms， 1999，15(2)：145-164
[31]C．Adjih， P．Jacquet， L．Viennot．Computing connected dominated sets with multipoint relays．Ad Hoc & Sensor Networks， 2005， 1(1)： 27-39
[32]D．M．Blough， M．Leoncini， G．Resta， P．Santi．The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks．IEEE Trans．on Mobile Computing， 2006， 5(9)：1267-1282
[33]P．Gupta， P．R．Kumar．Critical power for asymptotic connectivity in wireless networks．In： Fleming WH， McEneany WM， Yin G， Zhang Q， eds．Proc．of the Stochastic Analysis，Control， Optimization and Applications．Boston： Birkhauser， 1998， 547-566
[34]P．Santi， D．M．Blough．The critical transmitting range for connectivity in sparse wireless ad hoc networks．IEEE Trans．on Mobile Computing， 2003， 2(1)：25-39
[35]C．Adjih， P．Jacquet， L．Viennot．Computing connected dominated sets with multipoint relays．Ad Hoc & Sensor Networks， 2005， 1(1)： 27-39
[36]A．Qayyum， L．Viennot， A．Laouiti．Multipoint relaying for flooding broadcast message in mobile wireless networks．In：Sprague RH， Jr．， eds．Proc．of the 35th Hawaii Int'l Conf．System Sciences．Washington： IEEE Computer Society， 2002， 3898-3907
[37]L．Gewali， K．Mohamad， T．Min．Interference Aware Dominating Set for Sensor Network．Information Technology： New Generations， ITNG 2006．Third International Conference on，2006， 268-273
[38]S．Guha and S．Khuller．Approximation algorithms for connected dominating sets．Algorithmica， 1998， 20(4)：374-387
[39]M．V．Marathe， H．Breu， H．B．Hunt Ⅲ， et al．．Simple heuristics for unit disk graphs，Networks， 1995， 25： 59-68
[40]P．J．Wan， K．Alzoubi， and O．Frieder．Distributed construction of connected dominating set in wireless ad hoc networks．Proc．of IEEE INFOCOM'2002， 2002， 3： 1597-1604
[41]S．Funke， A．Kesselman， U．Meyer， M．Segal．A simple improved distributed algorithm for minimum CDS in unit disk graphs．ACM Transactions on Sensor Networks， 2006，2(3)：444-453
[42]A．Vahdatpour， F．Dabiri， M．Moazeni， and M．Sarrafzadeh．Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks．In： G．Taubenfeld (Ed．)， DISC 2008， LNCS 5218，2008，481-495
[43]M．G： Voronoi．Nouvelles applications des parametres continus a la theorie des formes quadratiques．Journal Fur Mathematik， 1908，134(3)：198-287
[44]A．H．Thiessen．Precipitation average for large area．Monthly Weather Review， 1911，39(7)：1082-1084
[45]P．J．Green， R．Sibson．Computing dirichlet tessellations in the plane．The Computer Journal，1977， 21(2)：168-173
[46]D．F．Watson．Computing the n-dimensional delaunay tessellation with application to voronoi polytopes．The Computer Journal， 1981， 24(2)：167-172
[47]M．I．Shamos， D．Hoey．Closest-Point problems．In： Proc．of the 16th Annual IEEE Symp．on FOCS．Washington： IEEE Computer Society， 1975， 151-162
[48]F．Aurenhammer．Voronoi diagrams—A survey ofafundamental geometric data structure．ACM Computing Surveys， 1991， 23(3)： 345-405
[49]W．B．Heinzelman， A．P．Chandrakasan， H．Balakrishnan．An application-specific protocol architecture for wireless microsensor networks．IEEE Trans．on Wireless Communications，2002， 1(4)：660-670
[50]路纲，周明天，牛新征，等．无线网络邻近图综述．软件学报，2008， 19(4)：888-911
[51]唐勇，周明天．基于极大独立集的最小连通支配集的分布式算法．电子学报，2007，35(5)：868-874
[52]T．W．Haynes， S．T．Hedetniemi， and P．J．Slater．Fundamentals of Domination in graphs．New York．Marcel Dekker Inc．， 1998
[53]M．Held and R．M．Karp．A dynamic programming approach to sequencing problems．Journal of SIAM， 1962， 10：196-210
[54]R．Tarjan and A．Trojanowski．Finding a maximum independent set．SIAM Journal on Computing， 6(3)：537-546， 1977
[55]C．Berge．The theory of graphs and its applications．Methuen & Co．： John Wiley & Sons，1962， 1-103
[56]E．J．Cockayne and S．T．Hedetniemi．Towards a theory of domination in graphs．Networks，1977， 7：247-261
[57]M．R．Garey and D．S．Johnson．Computers and Intractability： A Guide to the Theory of NP-Completeness．New York： Freeman， 1979
[58]G．J．Chang and G．L．Nemhauser．The k-domination and k-stability problems in sun-free chordal graphs．S1AM J．Algebraic Discrete Methods， 1984， 5：332-345
[59]Miroslav Chlebik，Janka Chlebikova．Approximation Hardness of Dominating Set Problems．S．Albers and T．Radzik (Eds．)： ESA 2004， LNCS 3221， 2004， 192-203
[60]M．M．Halldoresson．Approximating the Minimum Maximal Independence Number．Inf．Process．Lett．， 46， 1993， 169-172
[61]J．Hastad．Clique is hard to approximate within n~(1-ε) ．Foundations of Computer Science，1996．Proceedings．， 37th Annual Symposium on．1996， 627-636
[62]B．Reed．Paths， stars and the number three．Combinatorics， Probability and Computing， 1996，5， 277-295
[63]V．I．Arnautov．Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices ．Prikl．Mat．I Programmirovanie．1974， 11
[64]O．Ore．Theory of Graphs．Amer．Math．Soc．Colloq．Publ， 38 (Amer．Math．Soc， Providence，RI)， 1962，1-152
[65]H．B．Walikar， B．D．Acharya， and E．Sampathkumar．Recent develop-developments in the theory of domination in graphs．In MRI Lecture Notes in Math．， Mahta Research Instit．，Allahabad， 1979．1：1-72
[66]P．Flach and L．Volkmann．Estimations for the domination number of a graph．Discrete Math．，1990， 80：145-151
[67]S．T．Hedetniemi and R．C．Laskar．Connected domination in graphs．In B．Bollobas， editor，Graph Theory and Combinatorics， London： Academic Press， 1984， 209-218
[68]E．Sampathkumar and H．B．Walikar．The connected domination number of a graph．J．Math．Phys．Sci， 1979， 13：607-613
[69]D．J．Kleitman and D．B．West．Spanning trees with many leaves．SIAM．J．Discrete Math．，1991， 4：99-106
[70]E．Dahlhaus， J．Kratochvil， P．Manual， et al．．Transversal partitioning in balanced hypergraphs．Discrete Appl．Math．， 1997
[71]F．V．Fomin， D．Kratsch， G．J．Woeginger．Exact (Exponential) Algorithms for the Dominating Set Problem．Lecture Notes in Computer Science， 2004， 3353：245-256
[72]M．Davis and H．Putnam．A computing procedure for quanti_cation theory．Journal of the Association for Computing Machinery， 1960， 7：201-215
[73]F．Grandoni．A note on the complexity of minimum dominating set．Journal of Discrete Algorithms．2006，4(2)： 209-214
[74]F．V．Fomin， F．Grandoni， and D．Kratsch．Measure and conquer： Domination-a case study．In Proceedings of the 32nd International Colloquium on Automata， Languages and Programming (ICALP 2005)， LNCS， Berlin： Springer， 2005， 191-203
[75]D．Eppstein．Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms．ACM Transactions on Algorithms (TALG)， 2006， 2(4)： 492-509
[76]J．M．Robson．Algorithms for maximum independent sets．Journal of Algorithms， 1986，7(3)：425-440
[77]F．V．Fomin， F．Grandoni， A．V．Pyatkin， et al．．Bounding the Number of Minimal Dominating Sets： A Measure and Conquer Approach．Algorithms and Computation， 2005， 3827： 573-582
[78]F．V．Fomin， F．Grandoni， A．V．Pyatkin， et al．．Combinatorial Bounds via Measure and Conquer： Bounding Minimal Dominating Sets and Applications．Proc．16th ISAAC， 2006，1-14
[79]F．V．Fomin， F．Grandoni， D．Kratsch．Measure and conquer： a simple O(20．288n) independent set algorithm．Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm， 2006， 18-25
[80]T．Jian．An O(20．304n) algorithm for solving maximum independent set problem．IEEE Transactions on Computers， 1986， 35(9)：847-851
[81]R．Beigel．Finding maximum independent sets in sparse and general graphs．Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA' 1999)，1999，856-857
[82]F．V．Fomin， F．Grandoni， D．Kratsch．Solving Connected Dominating Set Faster Than 2n．S．Arun-Kumar and N．Garg (Eds．)： FSTTCS 2006， LNCS 4337， 2006， 152-163
[83]S．Gaspers， M．Liedlof．A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs．F．V．Fomin (Ed．)： WG 2006， Berlin Heidelberg：Springer-Verlag 2006， 78-89
[84]F．V．Fomin， A．A．Stepanov．Counting Minimum Weighted Dominating Sets．G．Lin (Ed．)： COCOON 2007， LNCS 4598， Berlin Heidelberg： Springer-Verlag， 2007， 165-175
[85]U．SchAoning．Algorithmics in exponential time．In Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005)， vol．3404 of LNCS， Berlin： Springer，2005， 36-43
[86]G．Woeginger．Exact algorithms for NP-hard problems： A survey．In Combinatorial Optimization-Eureka， you shrink!， vol．2570 of LNCS， Berlin： Springer-Verlag， 2003，185-207
[87]J．W．Moon， L．Moser．On cliques in graphs．Israel J．Math．，1965， 3， 23-28 [88]M．Furey．A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs．J．R．Correa， A．Hevia， and M．Kiwi (Eds．)： LATIN 2006， LNCS 3887，2006，491-501
[89]V．Dahll(o|¨)f， P．Jonsson．An algorithm for counting maximum weighted independent sets and its applications．Symposium on Discrete Algorithms，Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms， 2002， 292-298
[90]D．Kratsch and M．Liedloff．An Exact Algorithm for the Minimum．Dominating Clique Problem．H．L．Bodlaender and M．A．Langston (Eds．)： IWPEC 2006， LNCS 4169， 2006，130-141
[91]Chi-Tsun Cheng， Chi K．Tse， and Francis C．M．Lau．A Tree-Based Data Collecting Network Structure for Wireless Sensor Networks．JESTC， 2008， 6(3)： 210-213
[92]1．Cidon and O．Mokryn．Propagation and leader election in multihop broadcast environment．Proc．of 12th International Symposium on DIStributed Computing (DISC98)， September 1998， 104-119
[93]A．Roxin， J．Gaber， M．Wack， and A．Nait-Sidi-Moh．Survey of Wireless Geolocation Techniques．Globecom Workshops， 2007， New York： IEEE Computer Society， 2007， 1-9
[94]G．1．Sun， J．Chen， W．Guo， and K．J．Ray Liu．Signal processing techniques in network-aided positioning： a survey of state-of-the-art positioning designs．Signal Processing Magazine，IEEE， 2005， 22(4)：12-23
[95]H．Liu， H．S．Darabi， P．Banerjee， and J．Liu．Survey of Wireless Indoor Positioning Techniques and Systems．Systems， Man， and Cybernetics， Part C： Applications and Reviews，IEEE Transactions on， 2007， 37(6)：1067-1080
[96]K．Yedavalli and B．Krishnamachari．Sequence-Based Localization in Wireless Sensor Networks．IEEE transactions on Mobile Computing， 2008， 7(1)：81-94
[97]李建中，李金宝，石胜飞．传感器网络与感知数据管理的概念、问题与进展．软件学报，2003， 14(10)：1717-1727
[98]C．Intanagonwiwat， R．Govindan， D．Estrin， et al．．Directed diffusion for wireless sensor networking．IEEE/ACM Trans．on Networking， 2003， 11(1)：2-16
[99]唐勇，周明天，张欣．无线传感器网络路由协议研究进展．软件学报，2006，17(3)：410-421
[100]J．H．Chang， L．Tassiulas．Maximum lifetime routing in wireless sensor networks．IEEE/ACM Trans．on Networking， 2004， 12(4)： 609-619
[101]M．Bhardwaj， A．P．Chandrakasan．Bounding the lifetime of sensor networks via optimal role assignments．In： Kermani P， Lee D， Orda A， eds．The 21st Annual Joint Conf．of the IEEE Computer and Communications Societies．Washington： IEEE Computer Society， 2002，1587-1596
[102]V．Rai， R．N．Mahapatra．Lifetime modeling of a sensor network．In： Pedram M， Aynsley AF，eds．Proc．of the Design， Automation and Test in Europe．Washington：IEEE Computer Society， 2005， 202-203
[103]D．M．Blough， P．Santi．Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary adhoc networks．In： Akyildiz JF， Lin JYB， Jain J， eds．ACM Mobicom 2002．New York： ACM Press， 2002， 183-192
[104]H．H．Zhang， J．Hou．On the upper bound of α-lifetime for large sensor networks．ACM Trans．on Sensor Networks， 2005， 1(2)： 272-300
[105]M．Busse， T．Haenselmann， W．Effelsberg．A comparison of lifetime-efficient forwarding strategies for wireless sensor networks．In： Proc．of the 3rd ACM Int'l Workshop on Performance Evaluation of Wireless Ad Hoc， Sensor and Ubiquitous Networks， 2006， 33-40
[106]K．K．Ramachandran， B．Sikda．A population based approach to model network lifetime in wireless sensor networks．In： Squillante MS， ed．ACM SIGMETRICS Performance Evaluation Review．New York： ACM Press， 2005， 21-23
[107]周明天，谭良．可信计算及其进展．电子科技大学学报．2006， 35(4)：686-697
[108]D．Michelucci， J．M．Moreau．Lazy arithmetic．IEEE Transactions on Computers， 1997， 46(9)961-975
[109]周培德．计算几何算法设计与分析(3版)．北京：清华大学出版社．2008，1-300
[110]CGAL project， http： www．cgal．org
[111]M．Overars．Designing the Computational Geometry Algorithms Library CGAL．In M．C．Lin and D．Manocha， editors．Applied Computational Geometry： Towards Geometric Engineering(WACG 96)， Berlin： Springer LNCS， 1996， 53-58
[112]C．Burnikel， R．Fleischer， K．Mehlhorn， et al．．Efficient Exact Geometric Computation Made Easy， Proceedings of the fifteenth annual symposium on Computational geometry， 1999，341-350
[113]M．Karavelas．2D voronoi diagram adaptor．In CGAL Editorial Board， editor， CGAL User and Reference Manual．(3．3 edition)， 2007
[114]qhull，http：//www．qhull．org/
[115]C．K．Yap．Robust geometric computation．In J．E．Goodman and J．O' Rourke．editors．Handbook of Discrete and Computational Geometry chapter 35．CRC Press LLC，1997，653-668
[116]C．M．Hoffmann．The problems of accuracy and robustness in geometric computation．Computer， 1989， 22(3)：31-39
[117]S．J．Fortune， C．J．Van Wyk．Efficient exact arithmetic for computational geometry．ACM Proceedings of the ninth annual symposium on Computational geometry．1993， 163-172
[118]H．Bronnimann， I．Z．Emiris， V．Y．Pan， P．Pion．Computing exact geometric predicates using modular arithmetic with single precision．Proceedings of the thirteenth annual symposium on Computational geometry， 1997， 174-182
[119]S．J．Fortune and C．J．Van Wyk．Static analysis yields efficient exact integer arithmetic for computational geometry．ACM Trans．Graph， 1996， 15(3)：223-248
[120]O．Devillers and M．Teillaud．Perturbations and vertex removal in a 3D Delaunay triangulation．In Proc．14th ACM SIAM Sympos．Discrete Algorithms (SODA)， 2003，313-319
[121]R．Seidel．The nature and meaning of perturbations in geometric computing．Discrete Comput．Geom．， 1998， 19(1)：1-17
[122]D．Greene and F．Yao．Finite Resolution Computational Geometry．Proc．27th IEEE Symp．Foundations of Computer Science， 1986， 143-152
[123]M．O．Benouamer， P．Jaillon， D．Michelucci， J．M．Moreau．A lazy exact arithmetic．IEEE 11th Symposium on Computer Arithmetic， 1993， 242-249
[124]H．Bronnimann， M．Yvinec．Efficient exact evaluation of signs of determinants．Proceedings of the thirteenth annual symposium on Computational geometry， 1997， 166-173
[125]K．Sugihara．Toward super robust geometric computation．Proceedings of the 2008 ACM symposium on Solid and physical modeling．2008， 11-12
[126]P．Bahl and V．N．Padmanabhan．RADAR： An In-Building RF-Based User Location and Tracking System．In Proceedings of the IEEE INFOCOM '00， March 2000，http：//www．es．indiana．edu/～connelly/Docs/radar．pdf
[127]T．S．Rappaport．Wireless Communications， Principles & Practice， 2ed．Prentice Hall， 2001， 69-138
[128]路纲，周明天，佘堃，等．无线传感器网络路由协议的寿命分析．软件学报，2009(2)：375-393．http：//www．jos．org．cn/1000-9825/3180．htm
[129]B．H．Wellenhoff， H．Lichtenegger and J．Collins．Global Positions System： Theory and Practice， Fourth Edition．Springer Verlag， 1997， 1-65
[130]G．Mao， B．Fidan， and B．D．O．Anderson．Wireless Sensor Network Localization Techniques．Computer Networks， July 2007， 51(10)： 2529-2553
[131]A．Ward，A．Jones， and A．Hopper．A new location technique for the active office．IEEE Personal Communications， 1997， 4(5)： 42-47
[132]N．B．Priyantha， A．Chakraborty and H．Balakrishnan．The Cricket Location-Support System．In Proceedings of MOBICOM '00， New York， August 2000，http：//www2．dc．ufscar．br/～regina/Recursosubicom/cricket．pdf
[133]D．Niculescu and B．Nath．Ad hoc positioning system (APS) using AOA．Proceedings of IEEE INFOCOM， 2003
[134]R．Want， A．Hopper， V．Falcao， J．Gibbons．The active badge location system．ACM Trans．on Information Systems， 1992， 10(1)： 91-102
[135]A．Savvides， C．C．Han and M．B．Srivastava．Dynamic Fine- Grained Localization in Ad-Hoc Networks of Sensors．In Proceedings of MOBICOM '01， 2001， July 2001， 166-179
[136] A. Savvides, H. Park and M. Srivastava. The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems. In First ACM International Workshop on Wireless Sensor Networks and Application, Atlanta, GA, September 2002
[137] C. Savarese, J. M. Rabaey, J. Beutel. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int'l Conf. on Acoustics, Speech, and Signal, 2001, 4: 2037-2040
[138] C. Savarese, J. Rabay, K. Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. Proc. of the USENIX Technical Annual Conf, 2002, 317-327
[139] S. Meguerdichian, S. Slijepcevic, V. Karayan, M. Potkonjak. Localized algorithms in wireless ad-hoc networks: Location discovery and sensor exposure. In: Proc. of the 2nd ACM Int'1 Symp. on Mobile Ad Hoc Networking & Computing, 2001, 106-116
[140] N. B. Priyantha, H. Balakrishnan, E. D. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. Proceedings of IEEE INFOCOM, 2005
[141] D. Niculescu and B. Nath. Dv based positioning in ad hoc networks. Journal of Telecommunication Systems, January 2003, 22(1): 267-280
[142] D. Niculescu and B. Nath. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf, 2001, 5: 2926-2931
[143] D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AoA. In: Proc. of the IEEE INFOCOM 2003,2003, 1734-1743
[144] L. Doherty, K. S. J. Pister, L. El Ghaoui. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001, 2001, 3:1655-1663
[145] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine, October 2000, 7(5): 28-34
[146] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher. Range-free localization and its impact on large scale sensor networks. ACM Transactions on Embedded Computing Systems, 2005, 4(4): 877-906
[147] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz. Localization from mere connectivity Proceedings of the 4th ACM international Symposium on Mobile ad hoc networking & computing, 2003, 201-212
[148] M. Nicoli, C. Morelli, V. Rampa. A Jump Markov Particle Filter for Localization of Moving Terminals in Multipath Indoor Scenarios. Signal Processing, IEEE Transactions on, Part 1, Aug. 2008, 56(8): 3801-3809
[149]S．H．Fang， T．N．Lin．Indoor Location System Based on Discriminant-Adaptive Neural Network in IEEE 802．11 Environments．Neural Networks， IEEE Transactions on， Nov．2008，19(11)： 1973-1978
[150]J．Kosecka， F．Li．Vision based topological Markov localization．Robotics and Automation，2004， Proceedings， ICRA '04， 2004 IEEE International Conference on， 2004， 2：1481-1486
[2]H．Breu， D．G．Kirkpatrick．Unit disk graph recognition is NP-hard．Computational Geometry Theory and Applications， 1998， 9 (1-2)： 3-24
[3]F．P．Preparata and M．I．Shamos．Computational geometry-an introduction．New York：Springer-Verlag， 1985， 1-205
[4]A．C．Yao．On constructing minimum spanning trees in k-dimensional spaces and related problems．SIAM Journal Computing， 1982，11(4)：721-736
[5]M．D．Penrose．The longest edge of the random minimal spanning tree．The Annals of Applied Probability， 1997， 7(2)：340-361
[6]E．N．Gilbert， H．O．Pollak．Steiner minimal trees．SIAM Journal on Applied Mathematics， 1968， 16(1)：1-29
[7]D．Z．Du， F．K．Hwang．A proof of gilbert-pollack's conjecture on the steiner ratio．Algorithmica， 1992， 7：121-135
[8]R．M．Karp．Reducibility among combinatorial problems．In： R．E．Miller， J．W．Thatcher， eds．Proc．of the Complexity of Computer Computations， New York： Plenum Press， 1972， 85-103
[9]M．R．Garey， R．L．Graham， D．S．Johnson．The complexity of computing Steiner minimal trees．SIAM Journal on Applied Mathematics， 1977， 32(4)：835-859
[10]N．Meghanathan．Determining a sequence of stable multicast Steiner trees in mobile ad hoc networks．In： Menezes R， ed．ACM Proc．of the 44th Annual Southeast Regional Conf．New York： ACM Press， 2006， 102-106
[11]A．A．-K Jeng， 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， 2007，18(4)：536-549
[12]P．Bose， L．Devroye， W．Evans， D．Kirkpatrick．On the spanning ratio of gabriel graphs and beta-skeletons．In： Rajsbaum S， ed．Proc．of the Latin．Theoretical Informatics Conf．Berlin：Springer-Verlag， 2002，479-493
[13]K．J．Supowit．The relative neighborhood graph， with an application to minimum spanning trees．Journal of Association for Computing Machinery， 1983， 30(3)：428-448
[14]G．T．Toussaint．The relative neighborhood graph of a finite planar set．Pattern Recognition，1980， 12(4)：261-268
[15]K．R．Gabriel， R．R．Sokal．A new statistical approach to geographic variation analysis．Systematic Zoology， 1969， 18(3)：259-278
[16]X．Y．Li， P．J．Wan， Y．Wang， O．Frieder．Sparse power efficient topology for wireless networks．In： Sprague RH， Jr．， eds．Proc．of the 35th Annual Hawaii Intl Conf on System Sciences．Washington： IEEE Computer Society， 2002， 296-306
[17]P．J．Wan， C．W．Y．On the longest edge of gabriel graphs in wireless ad hoc networks．IEEE Trans．on Parallel and Distributed Systems， 2007， 18(1)：111-125
[18]X．Y．Li， G．Calinescu， P．J．Wan， Y．Wang．Localized delaunay triangulation with application in ad hoc wireless networks．IEEE Trans．on Parallel and Distributed Systems， 2003，14(10)：1035-1047
[19]X．Y．Li， G．Calinescu， P．J．Wan．Distributed construction of planar spanner and routing for ad hoc wireless networks．In： Kermani P， Lee D， Orda A， eds．Proc．of the 21st Annual Joint Conf of the IEEE Computer and Communications Societies．Washington：IEEE Computer Society， 2002， 1268-1277
[20]P．Santi．Topology control in wireless ad hoc and sensor networks．ACM Computing Surveys， 2005， 37(2)：164-194
[21]S．Ruhrup， C．Schindelhauer， K．Volbert， M．Grunewald．Performance of distributed algorithms for topology control in wireless networks．In： Werner B， ed．Proc．of the IEEE Parallel and Distributed Processing Symp．Dublin： Broadcom Eireann Res．Ltd．， 2003，582-590
[22]R．Wattenhofer， L．Li， P．Bahl， Y．M．Wang．Distributed topology control for power efficient operation in multihop wireless ad hoc networks．In： Sengupta B， Kermani P， Lee D， eds．Proc of the 20th Annual Joint Conf．of the IEEE Computer and Communications Societies．Washington： IEEE Computer Society， 2001， 1388-1397
[23]L．Li， J．Y．Halpern， P．Bahl， et al．．Analysis of a cone-based distributed topology control algorithm for wireless multihop networks．In： Kshemkalyani A， Shavit N， eds．ACM Proc．of the 20th Annual Symp．on Principles of Distributed Computing．New York： ACM Press，2001， 264-273
[24]N．Li， J．C．Hou， S．Lui．Design and analysis of an mst-based topology control algorithm．IEEE Trans．on Wireless Communications， 2005， 4(3)：1195-1206
[25]V．Rodoplu， T．H．Meng．Minimum energy mobile wireless networks．IEEE J．Sel．Areas Communication， 1999， 17(8)：1333-1344
[26]L．Li， J．Y．Halpern．Minimum-Energy mobile wireless networks revisited．Communications．In： Shahin MK， ed．Proc．of the IEEE Int'l Conf．on Communacations (ICC 2001)．Washington： IEEE Computer Society， 2001， 278-283
[27]D．England， B．Veeravalli， J．B．Weissman．A robust spanning tree topology for data collection and dissemination in distributed environments．IEEE Trans．on Parallel and Distributed Systems， 2007， 18(5)：608-620
[28]M．Burkhart， P．von Rickenbach， R．Wattenhofer， et al．．Does topology control reduce interference? In： Murai J， Perkins C， Tassiulas L， eds．Proc．of the 5th ACM Int'1 Symp．on Mobile Ad Hoc Networking and Computing．New York： ACM Press， 2004， 9-19
[29]N．Li， J．C．Hou．Localized fault-tolerant topology control in wireless ad hoc networks．IEEE Trans．on Parallel and Distributed Systems， 2006， 17(4)：307-320
[30]M．D．Penrose．On K-connecitivity for a geometric random graph．Random Structures and Algorithms， 1999，15(2)：145-164
[31]C．Adjih， P．Jacquet， L．Viennot．Computing connected dominated sets with multipoint relays．Ad Hoc & Sensor Networks， 2005， 1(1)： 27-39
[32]D．M．Blough， M．Leoncini， G．Resta， P．Santi．The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks．IEEE Trans．on Mobile Computing， 2006， 5(9)：1267-1282
[33]P．Gupta， P．R．Kumar．Critical power for asymptotic connectivity in wireless networks．In： Fleming WH， McEneany WM， Yin G， Zhang Q， eds．Proc．of the Stochastic Analysis，Control， Optimization and Applications．Boston： Birkhauser， 1998， 547-566
[34]P．Santi， D．M．Blough．The critical transmitting range for connectivity in sparse wireless ad hoc networks．IEEE Trans．on Mobile Computing， 2003， 2(1)：25-39
[35]C．Adjih， P．Jacquet， L．Viennot．Computing connected dominated sets with multipoint relays．Ad Hoc & Sensor Networks， 2005， 1(1)： 27-39
[36]A．Qayyum， L．Viennot， A．Laouiti．Multipoint relaying for flooding broadcast message in mobile wireless networks．In：Sprague RH， Jr．， eds．Proc．of the 35th Hawaii Int'l Conf．System Sciences．Washington： IEEE Computer Society， 2002， 3898-3907
[37]L．Gewali， K．Mohamad， T．Min．Interference Aware Dominating Set for Sensor Network．Information Technology： New Generations， ITNG 2006．Third International Conference on，2006， 268-273
[38]S．Guha and S．Khuller．Approximation algorithms for connected dominating sets．Algorithmica， 1998， 20(4)：374-387
[39]M．V．Marathe， H．Breu， H．B．Hunt Ⅲ， et al．．Simple heuristics for unit disk graphs，Networks， 1995， 25： 59-68
[40]P．J．Wan， K．Alzoubi， and O．Frieder．Distributed construction of connected dominating set in wireless ad hoc networks．Proc．of IEEE INFOCOM'2002， 2002， 3： 1597-1604
[41]S．Funke， A．Kesselman， U．Meyer， M．Segal．A simple improved distributed algorithm for minimum CDS in unit disk graphs．ACM Transactions on Sensor Networks， 2006，2(3)：444-453
[42]A．Vahdatpour， F．Dabiri， M．Moazeni， and M．Sarrafzadeh．Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks．In： G．Taubenfeld (Ed．)， DISC 2008， LNCS 5218，2008，481-495
[43]M．G： Voronoi．Nouvelles applications des parametres continus a la theorie des formes quadratiques．Journal Fur Mathematik， 1908，134(3)：198-287
[44]A．H．Thiessen．Precipitation average for large area．Monthly Weather Review， 1911，39(7)：1082-1084
[45]P．J．Green， R．Sibson．Computing dirichlet tessellations in the plane．The Computer Journal，1977， 21(2)：168-173
[46]D．F．Watson．Computing the n-dimensional delaunay tessellation with application to voronoi polytopes．The Computer Journal， 1981， 24(2)：167-172
[47]M．I．Shamos， D．Hoey．Closest-Point problems．In： Proc．of the 16th Annual IEEE Symp．on FOCS．Washington： IEEE Computer Society， 1975， 151-162
[48]F．Aurenhammer．Voronoi diagrams—A survey ofafundamental geometric data structure．ACM Computing Surveys， 1991， 23(3)： 345-405
[49]W．B．Heinzelman， A．P．Chandrakasan， H．Balakrishnan．An application-specific protocol architecture for wireless microsensor networks．IEEE Trans．on Wireless Communications，2002， 1(4)：660-670
[50]路纲，周明天，牛新征，等．无线网络邻近图综述．软件学报，2008， 19(4)：888-911
[51]唐勇，周明天．基于极大独立集的最小连通支配集的分布式算法．电子学报，2007，35(5)：868-874
[52]T．W．Haynes， S．T．Hedetniemi， and P．J．Slater．Fundamentals of Domination in graphs．New York．Marcel Dekker Inc．， 1998
[53]M．Held and R．M．Karp．A dynamic programming approach to sequencing problems．Journal of SIAM， 1962， 10：196-210
[54]R．Tarjan and A．Trojanowski．Finding a maximum independent set．SIAM Journal on Computing， 6(3)：537-546， 1977
[55]C．Berge．The theory of graphs and its applications．Methuen & Co．： John Wiley & Sons，1962， 1-103
[56]E．J．Cockayne and S．T．Hedetniemi．Towards a theory of domination in graphs．Networks，1977， 7：247-261
[57]M．R．Garey and D．S．Johnson．Computers and Intractability： A Guide to the Theory of NP-Completeness．New York： Freeman， 1979
[58]G．J．Chang and G．L．Nemhauser．The k-domination and k-stability problems in sun-free chordal graphs．S1AM J．Algebraic Discrete Methods， 1984， 5：332-345
[59]Miroslav Chlebik，Janka Chlebikova．Approximation Hardness of Dominating Set Problems．S．Albers and T．Radzik (Eds．)： ESA 2004， LNCS 3221， 2004， 192-203
[60]M．M．Halldoresson．Approximating the Minimum Maximal Independence Number．Inf．Process．Lett．， 46， 1993， 169-172
[61]J．Hastad．Clique is hard to approximate within n~(1-ε) ．Foundations of Computer Science，1996．Proceedings．， 37th Annual Symposium on．1996， 627-636
[62]B．Reed．Paths， stars and the number three．Combinatorics， Probability and Computing， 1996，5， 277-295
[63]V．I．Arnautov．Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices ．Prikl．Mat．I Programmirovanie．1974， 11
[64]O．Ore．Theory of Graphs．Amer．Math．Soc．Colloq．Publ， 38 (Amer．Math．Soc， Providence，RI)， 1962，1-152
[65]H．B．Walikar， B．D．Acharya， and E．Sampathkumar．Recent develop-developments in the theory of domination in graphs．In MRI Lecture Notes in Math．， Mahta Research Instit．，Allahabad， 1979．1：1-72
[66]P．Flach and L．Volkmann．Estimations for the domination number of a graph．Discrete Math．，1990， 80：145-151
[67]S．T．Hedetniemi and R．C．Laskar．Connected domination in graphs．In B．Bollobas， editor，Graph Theory and Combinatorics， London： Academic Press， 1984， 209-218
[68]E．Sampathkumar and H．B．Walikar．The connected domination number of a graph．J．Math．Phys．Sci， 1979， 13：607-613
[69]D．J．Kleitman and D．B．West．Spanning trees with many leaves．SIAM．J．Discrete Math．，1991， 4：99-106
[70]E．Dahlhaus， J．Kratochvil， P．Manual， et al．．Transversal partitioning in balanced hypergraphs．Discrete Appl．Math．， 1997
[71]F．V．Fomin， D．Kratsch， G．J．Woeginger．Exact (Exponential) Algorithms for the Dominating Set Problem．Lecture Notes in Computer Science， 2004， 3353：245-256
[72]M．Davis and H．Putnam．A computing procedure for quanti_cation theory．Journal of the Association for Computing Machinery， 1960， 7：201-215
[73]F．Grandoni．A note on the complexity of minimum dominating set．Journal of Discrete Algorithms．2006，4(2)： 209-214
[74]F．V．Fomin， F．Grandoni， and D．Kratsch．Measure and conquer： Domination-a case study．In Proceedings of the 32nd International Colloquium on Automata， Languages and Programming (ICALP 2005)， LNCS， Berlin： Springer， 2005， 191-203
[75]D．Eppstein．Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms．ACM Transactions on Algorithms (TALG)， 2006， 2(4)： 492-509
[76]J．M．Robson．Algorithms for maximum independent sets．Journal of Algorithms， 1986，7(3)：425-440
[77]F．V．Fomin， F．Grandoni， A．V．Pyatkin， et al．．Bounding the Number of Minimal Dominating Sets： A Measure and Conquer Approach．Algorithms and Computation， 2005， 3827： 573-582
[78]F．V．Fomin， F．Grandoni， A．V．Pyatkin， et al．．Combinatorial Bounds via Measure and Conquer： Bounding Minimal Dominating Sets and Applications．Proc．16th ISAAC， 2006，1-14
[79]F．V．Fomin， F．Grandoni， D．Kratsch．Measure and conquer： a simple O(20．288n) independent set algorithm．Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm， 2006， 18-25
[80]T．Jian．An O(20．304n) algorithm for solving maximum independent set problem．IEEE Transactions on Computers， 1986， 35(9)：847-851
[81]R．Beigel．Finding maximum independent sets in sparse and general graphs．Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA' 1999)，1999，856-857
[82]F．V．Fomin， F．Grandoni， D．Kratsch．Solving Connected Dominating Set Faster Than 2n．S．Arun-Kumar and N．Garg (Eds．)： FSTTCS 2006， LNCS 4337， 2006， 152-163
[83]S．Gaspers， M．Liedlof．A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs．F．V．Fomin (Ed．)： WG 2006， Berlin Heidelberg：Springer-Verlag 2006， 78-89
[84]F．V．Fomin， A．A．Stepanov．Counting Minimum Weighted Dominating Sets．G．Lin (Ed．)： COCOON 2007， LNCS 4598， Berlin Heidelberg： Springer-Verlag， 2007， 165-175
[85]U．SchAoning．Algorithmics in exponential time．In Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005)， vol．3404 of LNCS， Berlin： Springer，2005， 36-43
[86]G．Woeginger．Exact algorithms for NP-hard problems： A survey．In Combinatorial Optimization-Eureka， you shrink!， vol．2570 of LNCS， Berlin： Springer-Verlag， 2003，185-207
[87]J．W．Moon， L．Moser．On cliques in graphs．Israel J．Math．，1965， 3， 23-28 [88]M．Furey．A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs．J．R．Correa， A．Hevia， and M．Kiwi (Eds．)： LATIN 2006， LNCS 3887，2006，491-501
[89]V．Dahll(o|¨)f， P．Jonsson．An algorithm for counting maximum weighted independent sets and its applications．Symposium on Discrete Algorithms，Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms， 2002， 292-298
[90]D．Kratsch and M．Liedloff．An Exact Algorithm for the Minimum．Dominating Clique Problem．H．L．Bodlaender and M．A．Langston (Eds．)： IWPEC 2006， LNCS 4169， 2006，130-141
[91]Chi-Tsun Cheng， Chi K．Tse， and Francis C．M．Lau．A Tree-Based Data Collecting Network Structure for Wireless Sensor Networks．JESTC， 2008， 6(3)： 210-213
[92]1．Cidon and O．Mokryn．Propagation and leader election in multihop broadcast environment．Proc．of 12th International Symposium on DIStributed Computing (DISC98)， September 1998， 104-119
[93]A．Roxin， J．Gaber， M．Wack， and A．Nait-Sidi-Moh．Survey of Wireless Geolocation Techniques．Globecom Workshops， 2007， New York： IEEE Computer Society， 2007， 1-9
[94]G．1．Sun， J．Chen， W．Guo， and K．J．Ray Liu．Signal processing techniques in network-aided positioning： a survey of state-of-the-art positioning designs．Signal Processing Magazine，IEEE， 2005， 22(4)：12-23
[95]H．Liu， H．S．Darabi， P．Banerjee， and J．Liu．Survey of Wireless Indoor Positioning Techniques and Systems．Systems， Man， and Cybernetics， Part C： Applications and Reviews，IEEE Transactions on， 2007， 37(6)：1067-1080
[96]K．Yedavalli and B．Krishnamachari．Sequence-Based Localization in Wireless Sensor Networks．IEEE transactions on Mobile Computing， 2008， 7(1)：81-94
[97]李建中，李金宝，石胜飞．传感器网络与感知数据管理的概念、问题与进展．软件学报，2003， 14(10)：1717-1727
[98]C．Intanagonwiwat， R．Govindan， D．Estrin， et al．．Directed diffusion for wireless sensor networking．IEEE/ACM Trans．on Networking， 2003， 11(1)：2-16
[99]唐勇，周明天，张欣．无线传感器网络路由协议研究进展．软件学报，2006，17(3)：410-421
[100]J．H．Chang， L．Tassiulas．Maximum lifetime routing in wireless sensor networks．IEEE/ACM Trans．on Networking， 2004， 12(4)： 609-619
[101]M．Bhardwaj， A．P．Chandrakasan．Bounding the lifetime of sensor networks via optimal role assignments．In： Kermani P， Lee D， Orda A， eds．The 21st Annual Joint Conf．of the IEEE Computer and Communications Societies．Washington： IEEE Computer Society， 2002，1587-1596
[102]V．Rai， R．N．Mahapatra．Lifetime modeling of a sensor network．In： Pedram M， Aynsley AF，eds．Proc．of the Design， Automation and Test in Europe．Washington：IEEE Computer Society， 2005， 202-203
[103]D．M．Blough， P．Santi．Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary adhoc networks．In： Akyildiz JF， Lin JYB， Jain J， eds．ACM Mobicom 2002．New York： ACM Press， 2002， 183-192
[104]H．H．Zhang， J．Hou．On the upper bound of α-lifetime for large sensor networks．ACM Trans．on Sensor Networks， 2005， 1(2)： 272-300
[105]M．Busse， T．Haenselmann， W．Effelsberg．A comparison of lifetime-efficient forwarding strategies for wireless sensor networks．In： Proc．of the 3rd ACM Int'l Workshop on Performance Evaluation of Wireless Ad Hoc， Sensor and Ubiquitous Networks， 2006， 33-40
[106]K．K．Ramachandran， B．Sikda．A population based approach to model network lifetime in wireless sensor networks．In： Squillante MS， ed．ACM SIGMETRICS Performance Evaluation Review．New York： ACM Press， 2005， 21-23
[107]周明天，谭良．可信计算及其进展．电子科技大学学报．2006， 35(4)：686-697
[108]D．Michelucci， J．M．Moreau．Lazy arithmetic．IEEE Transactions on Computers， 1997， 46(9)961-975
[109]周培德．计算几何算法设计与分析(3版)．北京：清华大学出版社．2008，1-300
[110]CGAL project， http： www．cgal．org
[111]M．Overars．Designing the Computational Geometry Algorithms Library CGAL．In M．C．Lin and D．Manocha， editors．Applied Computational Geometry： Towards Geometric Engineering(WACG 96)， Berlin： Springer LNCS， 1996， 53-58
[112]C．Burnikel， R．Fleischer， K．Mehlhorn， et al．．Efficient Exact Geometric Computation Made Easy， Proceedings of the fifteenth annual symposium on Computational geometry， 1999，341-350
[113]M．Karavelas．2D voronoi diagram adaptor．In CGAL Editorial Board， editor， CGAL User and Reference Manual．(3．3 edition)， 2007
[114]qhull，http：//www．qhull．org/
[115]C．K．Yap．Robust geometric computation．In J．E．Goodman and J．O' Rourke．editors．Handbook of Discrete and Computational Geometry chapter 35．CRC Press LLC，1997，653-668
[116]C．M．Hoffmann．The problems of accuracy and robustness in geometric computation．Computer， 1989， 22(3)：31-39
[117]S．J．Fortune， C．J．Van Wyk．Efficient exact arithmetic for computational geometry．ACM Proceedings of the ninth annual symposium on Computational geometry．1993， 163-172
[118]H．Bronnimann， I．Z．Emiris， V．Y．Pan， P．Pion．Computing exact geometric predicates using modular arithmetic with single precision．Proceedings of the thirteenth annual symposium on Computational geometry， 1997， 174-182
[119]S．J．Fortune and C．J．Van Wyk．Static analysis yields efficient exact integer arithmetic for computational geometry．ACM Trans．Graph， 1996， 15(3)：223-248
[120]O．Devillers and M．Teillaud．Perturbations and vertex removal in a 3D Delaunay triangulation．In Proc．14th ACM SIAM Sympos．Discrete Algorithms (SODA)， 2003，313-319
[121]R．Seidel．The nature and meaning of perturbations in geometric computing．Discrete Comput．Geom．， 1998， 19(1)：1-17
[122]D．Greene and F．Yao．Finite Resolution Computational Geometry．Proc．27th IEEE Symp．Foundations of Computer Science， 1986， 143-152
[123]M．O．Benouamer， P．Jaillon， D．Michelucci， J．M．Moreau．A lazy exact arithmetic．IEEE 11th Symposium on Computer Arithmetic， 1993， 242-249
[124]H．Bronnimann， M．Yvinec．Efficient exact evaluation of signs of determinants．Proceedings of the thirteenth annual symposium on Computational geometry， 1997， 166-173
[125]K．Sugihara．Toward super robust geometric computation．Proceedings of the 2008 ACM symposium on Solid and physical modeling．2008， 11-12
[126]P．Bahl and V．N．Padmanabhan．RADAR： An In-Building RF-Based User Location and Tracking System．In Proceedings of the IEEE INFOCOM '00， March 2000，http：//www．es．indiana．edu/～connelly/Docs/radar．pdf
[127]T．S．Rappaport．Wireless Communications， Principles & Practice， 2ed．Prentice Hall， 2001， 69-138
[128]路纲，周明天，佘堃，等．无线传感器网络路由协议的寿命分析．软件学报，2009(2)：375-393．http：//www．jos．org．cn/1000-9825/3180．htm
[129]B．H．Wellenhoff， H．Lichtenegger and J．Collins．Global Positions System： Theory and Practice， Fourth Edition．Springer Verlag， 1997， 1-65
[130]G．Mao， B．Fidan， and B．D．O．Anderson．Wireless Sensor Network Localization Techniques．Computer Networks， July 2007， 51(10)： 2529-2553
[131]A．Ward，A．Jones， and A．Hopper．A new location technique for the active office．IEEE Personal Communications， 1997， 4(5)： 42-47
[132]N．B．Priyantha， A．Chakraborty and H．Balakrishnan．The Cricket Location-Support System．In Proceedings of MOBICOM '00， New York， August 2000，http：//www2．dc．ufscar．br/～regina/Recursosubicom/cricket．pdf
[133]D．Niculescu and B．Nath．Ad hoc positioning system (APS) using AOA．Proceedings of IEEE INFOCOM， 2003
[134]R．Want， A．Hopper， V．Falcao， J．Gibbons．The active badge location system．ACM Trans．on Information Systems， 1992， 10(1)： 91-102
[135]A．Savvides， C．C．Han and M．B．Srivastava．Dynamic Fine- Grained Localization in Ad-Hoc Networks of Sensors．In Proceedings of MOBICOM '01， 2001， July 2001， 166-179
[136] A. Savvides, H. Park and M. Srivastava. The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems. In First ACM International Workshop on Wireless Sensor Networks and Application, Atlanta, GA, September 2002
[137] C. Savarese, J. M. Rabaey, J. Beutel. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int'l Conf. on Acoustics, Speech, and Signal, 2001, 4: 2037-2040
[138] C. Savarese, J. Rabay, K. Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. Proc. of the USENIX Technical Annual Conf, 2002, 317-327
[139] S. Meguerdichian, S. Slijepcevic, V. Karayan, M. Potkonjak. Localized algorithms in wireless ad-hoc networks: Location discovery and sensor exposure. In: Proc. of the 2nd ACM Int'1 Symp. on Mobile Ad Hoc Networking & Computing, 2001, 106-116
[140] N. B. Priyantha, H. Balakrishnan, E. D. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. Proceedings of IEEE INFOCOM, 2005
[141] D. Niculescu and B. Nath. Dv based positioning in ad hoc networks. Journal of Telecommunication Systems, January 2003, 22(1): 267-280
[142] D. Niculescu and B. Nath. Ad-Hoc positioning systems (APS). In: Proc. of the 2001 IEEE Global Telecommunications Conf, 2001, 5: 2926-2931
[143] D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AoA. In: Proc. of the IEEE INFOCOM 2003,2003, 1734-1743
[144] L. Doherty, K. S. J. Pister, L. El Ghaoui. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001, 2001, 3:1655-1663
[145] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine, October 2000, 7(5): 28-34
[146] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher. Range-free localization and its impact on large scale sensor networks. ACM Transactions on Embedded Computing Systems, 2005, 4(4): 877-906
[147] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz. Localization from mere connectivity Proceedings of the 4th ACM international Symposium on Mobile ad hoc networking & computing, 2003, 201-212
[148] M. Nicoli, C. Morelli, V. Rampa. A Jump Markov Particle Filter for Localization of Moving Terminals in Multipath Indoor Scenarios. Signal Processing, IEEE Transactions on, Part 1, Aug. 2008, 56(8): 3801-3809
[149]S．H．Fang， T．N．Lin．Indoor Location System Based on Discriminant-Adaptive Neural Network in IEEE 802．11 Environments．Neural Networks， IEEE Transactions on， Nov．2008，19(11)： 1973-1978
[150]J．Kosecka， F．Li．Vision based topological Markov localization．Robotics and Automation，2004， Proceedings， ICRA '04， 2004 IEEE International Conference on， 2004， 2：1481-1486