微信服务号

微信订阅号

2025-4-15- 12
Home > Archive>Volume 19, Issue 4, 2008 >888-911
PDF HTML XML Export Cite reminder
A Survey of Proximity Graphs in Wireless Networks
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [49]
    • |
  • Related [20]
    • |
  • Cited by [21]
    • | |
  • Comments
    Abstract:

    Network topology can be represented by the proximity graph defined as a graph with a set of vertices V and a set of edges E such that a directed edge (u,v) belong to E if and only if the point v is in the neighborhood induced by some predefined proximity measures of point u. This paper reviews some important graphs obtained so far, and the contents mainly concentrated in five aspects of those proximity graphs including their definitions or conceptions, construction algorithms, illustrations, topological relationships, and some parameters. This paper also outlines several further research directions.

    Reference
    [1]Santi P,Blough DM.The critical transmitting range for connectivity in sparse wireless ad hoc networks.IEEE Trans.on Mobile Computing,2003,2(1):25-39.
    [2]Li XY,Wan PJ,Wang Y,Yi CW.Fault tolerant deployment and topology control in wireless networks.In:Gerla M,Ephremides A,Srivastava M,eds.Proc.of the 4th ACM Symp.on Mobile Ad Hoc Networking and Computing.New York:ACM Press,2003.117-128.
    [3]Preparata FP,Shamos MI.Computational Geometry-An Introduction.New York:Springer-Verlag,1985.10-454.
    [4]Yao AC.On constructing minimum spanning trees in k-dimensional spaces and related problems.SIAM Journal Computing,1982,11(4):721-736.
    [5]Penrose MD.The longest edge of the random minimal spanning tree.The Annals of Applied Probability,1997,7(2):340-361.
    [6]Gilbert EN,Pollak HO.Steiner minimal trees.SIAM Journal on Applied Mathematics,1968,16(1):1-29.
    [7]Du DZ,Hwang FK.A proof of gilbert-pollack's conjecture on the steiner ratio.Algorithmica,1992,7:121-135.
    [8]Garey MR,Johnson DS.The rectilinear steiner tree problem is np-complete.SIAM Journal on Applied Mathematics,1977,32(4):826-834.
    [9]Karp RM.Reducibility among combinatorial problems.In:Miller RE,Thatcher JW,eds.Proc.of the Complexity of Computer Computations.New York:Plenum Press,1972.85-103.
    [10]Garey MR,Graham RL,Johnson DS.The complexity of computing Steiner minimal trees.SIAM Journal on Applied Mathematics,1977,32(4):835-859.
    [11]Johnson DS.The NP-completeness column:The many limits on approximation.ACM Trans.on Algorithms,2006,2(3):473-489.
    [12]Aronov B,de Berg M,Otfried C,Gudmundsson J,Haverkort H,Vigneron A.Sparse geometric graphs with small dilation.In:Deng X,Du D,eds.Proc.of the 16th Int'l Symp.on Algorithms and Computation.Berlin:Springer-Verlag,2005.50-59.
    [13]Smid M.Geometric spanners with few edges and degree five.In:Jay B,Gudmundsson J,eds.Proc.of the 12th Computing:The Australasian Theory Symp.Darlinghurst:Australian Computer Society,Inc.,2006.1-3.
    [14]Liang WF.Approximate minimum-energy multicasting in wireless ad hoc networks.IEEE Trans.on Mobile Computing,2006,5(4):377-387.
    [15]Meghanathan N.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.
    [16]Toussaint GT.The relative neighborhood graph of a finite planar set.Pattern Recognition,1980,12(4):261-268.
    [17]Jeng AAK,Jan RH.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.
    [18]Bose P,Devroye L,Evans W,Kirkpatrick D.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.
    [19]Supowit KJ.The relative neighborhood graph,with an application to minimum spanning trees.Journal of Association for Computing Machinery,1983,30(3):428-448.
    [20]Gabriel KR,Sokal RR.A new statistical approach to geographic variation analysis.Systematic Zoology,1969,18(3):259-278.
    [21]Wan PJ,Yi CW.On the longest edge of gabriel graphs in wireless ad hoc networks.IEEE Trans.on Parallel and Distributed Systems,2007,18(1):111-125.
    [22]Li XY,Calinescu G,Wan PJ,Wang Y.Localized delaunay triangulation with application in ad hoc wireless networks.IEEE Trans.on Parallel and Distributed Systems,2003,14(10):1035-1047.
    [23]Li XY,Calinescu G,Wan PJ.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.
    [24]Chew LP.There is a planar graph almost as good as the complete graph.In:Agarwal A,ed.ACM Proc.of the 2nd Annual Symp.on Computational Geometry.New York:ACM Press,1986.169-177.
    [25]Santi P.Topology control in wireless ad hoc and sensor networks.ACM Computing Surveys,2005,37(2):164-194.
    [26]Li XY,Wan PJ,Wang Y,Frieder O.Sparse power efficient topology for wireless networks.In:Jr Sprague RH,ed.Proc.of the 35th Annual Hawaii Int'l Conf.on System Sciences.Washington:IEEE Computer Society,2002.296-306.
    [27]Ruhrup S,Schindelhauer C,Volbert K,Grunewald M.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.
    [28]Wattenhofer R,Li L,Bahl P,Wang YM.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.
    [29]Li L,Halpern JY,Bahl P,Wang YM,Wattenhofer R.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.
    [30]Li N,Hou JC,Lui S.Design and analysis of an mst-based topology control algorithm.IEEE Trans.on Wireless Communications,2005,4(3):1195-1206.
    [31]Rodoplu V,Meng TH.Minimum energy mobile wireless networks.IEEE J.Sel.Areas Communication,1999,17(8):1333-1344.
    [32]Li L,Halpern JY.Minimum-Energy mobile wireless networks revisited.In:Shahin MK,ed.Proc.of the IEEE Int'l Conf.on Communications (ICC 2001).Washington:IEEE Computer Society,2001.278-283.
    [33]England D,Veeravalli B,Weissman JB.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.
    [34]Burkhart M,von Rickenbach P,Wattenhofer R,Zollinger A.Does topology control reduce interference? In:Murai J,Perkins C,Tassiulas L,eds.Proc.of the 5th ACM Int'l Symp.on Mobile Ad Hoc Networking and Computing.New York:ACM Press,2004.9-19.
    [35]Li N,Hou JC.Localized fault-tolerant topology control in wireless ad hoc networks.IEEE Trans.on Parallel and Distributed Systems,2006,17(4):307-320.
    [36]Penrose MD.On K-connecitivity for a geometric random graph.Random Structures and Algorithms,1999,15(2):145-164.
    [37]Adjih C,Jacquet P,Viennot L.Computing connected dominated sets with multipoint relays.Ad Hoc & Sensor Networks,2005,1(1):27-39.
    [38]Blough DM,Leoncini M,Resta G,Santi P.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.
    [39]Gupta P,Kumar PR.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.
    [40]Garey MR,Johnson DS.Computers and Intractability:A Guide to the Theory of NP-Completeness.San Francisco:W.H.Freeman and Co.,1979.18-288.
    [41]Qayyum A,Viennot L,Laouiti A.Multipoint relaying for flooding broadcast message in mobile wireless networks.In:Jr Sprague RH,ed.Proc.of the 35th Hawaii Int'l Conf.System Sciences.Washington:IEEE Computer Society,2002.3898-3907.
    [42]Heinzelman WB,Chandrakasan AP,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks.IEEE Trans.on Wireless Communications,2002,1(4):660-670.
    [43]Voronoi MG.Nouvelles applications des parametres continus a la theorie des formes quadratiques.Journal Fur Mathematik,1908,134(3):198-287.
    [44]Thiessen AH.Precipitation average for large area.Monthly Weather Review,1911,39(7):1082-1084.
    [45]Green PJ,Sibson R.Computing dirichlet tessellations in the plane.The Computer Journal,1977,21(2):168-173.
    [46]Watson DF.Computing the n-dimensional delaunay tessellation with application to voronoi polytopes.The Computer Journal,1981,24(2):167-172.
    [47]Shamos MI,Hoey D.Closest-Point problems.In:Proc.of the 16th Annual IEEE Symp.on FOCS.Washington:IEEE Computer Society,1975.151-162.
    [48]Aurenhammer F.Voronoi diagrams-A survey of a fundamental geometric data structure.ACM Computing Surveys,1991,23(3):345-405.
    [49]Tang Y,Zhou MT.Maximal independent set based distributed algorithm for minimum connected dominating set.Chinese Journal of Electronics,2007,35(5):868-874 (in Chinese with English abstract).
    Comments
    Comments
    分享到微博
    Submit
Get Citation

路 纲,周明天,牛新征,佘 堃,唐 勇,秦 科.无线网络邻近图综述.软件学报,2008,19(4):888-911

Copy
Share
Article Metrics
  • Abstract:9102
  • PDF: 13167
  • HTML: 0
  • Cited by: 0
History
  • Received:July 22,2007
  • Revised:September 13,2007
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2035129Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063