无线网络邻近图综述

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.19,No.4,April2008,pp.878−901:[phone]©2008byJournalofSoftware.Allrightsreserved.无线网络邻近图综述∗路纲+,周明天,牛新征,佘堃,唐勇,秦科(电子科技大学计算机科学与工程学院,四川成都610054)ASurveyofProximityGraphsinWirelessNetworksLUGang+,ZHOUMing-Tian,NIUXin-Zheng,SHEKun,TANGYong,QINKe(CollegeofComputerScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China)+Correspondingauthor:Phn:[phone],E-mail:[e-mail],(4):878−901.:NetworktopologycanberepresentedbytheproximitygraphwhichwedefinedasagraphwithasetofverticesVandasetofedgesEsuchthatadirectededge(u,v)belongtoEifandonlyifthepointvisintheneighborhoodinducedbysomepredefindedproximitymeasuresofpointu.Inthisarticlewereviewsomeimportantgraphsobtainedsofar,andthecontentsmainlyconcentratedinfiveaspectsofthoseproximitygraphsincludingtheirdefinitionsorconceptions,constructionalgorithms,illustrations,topologicalrelationships,andsomeparameters.Beforetheend,wealsooutlineseveralfurtherresearchdirections.Applicationsofwirelessnetworkscanentirelychangethewayoflife,weconvincedthattheproximitygraphwillbeconsideredasafundamentalbuildingblockoftheforthcomingcenturyofpervasivecomputing,andwehopethispaperwillmotivateresearcherspaymoreattentiontothismagnificent,wonderfulandvaluableresearcharea.Keywords:proximitygraph;wirelessnetworks;topologycontrol;dominatingset;computationalgeometry摘要:网络拓扑结构可由邻近图表述,我们定义其为一个包含点集V和边集E的图,某有向边(u,v)属于该图当且仅当点v位于点u的邻域内,这个邻域是在某事先定义的邻近测度作用下产生的.回顾了迄今为止一些重要图结构,内容主要集中在5个方面,包括邻近图的定义或概念、构造算法、图例、隶属关系、拓扑参数,在结束之前还谈到进一步研究方向.无线网络应用将彻底改变人们生活的方式,我们确信,邻近图是即将到来的普适计算世纪的理论基石之一,期盼学者对这个有意义的研究领域给予更多关注.关键词:邻近图;无线网络;拓扑控制;支配集;计算几何中图法分类号:TP393文献标识码:A网络拓扑结构可由邻近图表述.邻近图作为无线网络信息处理的虚拟基础设施,对网络性能起决定性影响.在应用需求和计算机技术进步推动下,邻近图研究从上世纪60年代逐步兴起,涉及大量非常有趣而又有意义的问题,取得了丰硕研究成果,时至今日研究热度仍在上升,这体现在不断涌现的新成果上.邻近图不仅仅应∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60473090(国家自然科学基金);theNational11thFive-Year-Supproting-PlanofChinaunderGrantNo.2006BAH02A0407(国家“十一五”支撑计划)Received2007-07-22;Accepted2007-09-13路纲等:无线网络邻近图综述879用于无线网络,它在超大规模集成电路VLSI、纳米科技、控制导航、测量定位、生命科学等等领域都有着重大应用价值,这些领域代表本世纪高科技发展的重要方向,我们预测其研究热潮至少在本世纪内不会退却.本文主要从5个方面介绍无线网络领域常见或新近出现的邻近图结构,包括它们的含义、构造算法、图例、隶属关系、拓扑参数.本文第1节介绍一些预备知识.第2节具体说明每个图结构的定义、构造方法、性能特点、并根据我们的初步研究结果表达一些观点或看法,在第2节末尾小结邻近图与网络拓扑的关系等问题.第3节绘制文中所有邻近图的图例.第4节先总结图结构之间的拓扑隶属关系,然后列出代表性图结构重要拓扑参数的仿真结果.第5节谈到未来研究方向.第6节总结性结束全文.1预备知识1.1文中常用符号和术语的说明•M:通常,所有网络节点均匀随机分布在一个欧氏二维正方形平面域内,正方形的边长用M表示;•N,∂N:N为节点总数(不混淆时也指总节点);∂N代表距节点集凸边界不超过某预先设定距离的点;•n:某点u的逻辑邻节点数量,分别用n+,n−,n代表n的昀大值、昀小值、平均值;•λ:代表节点密度.本文中二维平面时,2NMλ=;•h:本文定义d维网络空间中的单位距离为1(,,,...)dhxyzλ=.此定义很有用,好处之一是使许多结果具有昀简形式.d=2时,MhN=.节点均匀分布时,h(x,y,z,…)=h是常数,与位置无关;•sink:规定只有一个,为距离网络域M右下角点昀近的节点;•G=(V,E):节点逻辑关系的图论表示方法,V,E分别表示点集和边集.用|•|表示集合•中元素个数;•N(u),N[u],Nk(u):分别代表点u的1跳邻节点、u∪N(u)、u的第k跳邻节点;•可平面图(planar):(本文范围内)G中除在顶点外边不交叉;•t-生成图G′(t-spanner):即V′=V,E′⊆E,分别用s′,s表示在G′,G中任意两相同点间路径距离,则存在常数t,使s′≤ts.有时候称G′为子图,G为超图;•psf,dsf,hsf:分别为power(distance,hop)stretchfactor的缩写,对应能量、距离、跳数——扩展因子,区别仅在于衡量代价的标准不同.如果G′是G的生成子图,用cost(u,v)表示从点u到点v路径的昀低代价,则图G′的扩展因子为,cos(,)maxcos(,)uvNGtfactorGt∈′′⎛⎞=⎜⎟⎝⎠uvuv,即所有点对在生成图和源图中昀短路径代价比的昀大值.用欧氏距离||||pathuv−∑替代cost就得到dsf,用距离的α次方||||pathuvα−∑替代cost就得到psf(α取决于信号传播方式,本文通常取α=2),用跳数uvpathhop→∑替代cost就得到hsf.•w.h.p.:withhighprobability的缩写,如果某事件以1(或某个接近1的值)为概率发生.记法取自文献[1].1.2考察邻近图的若干准则在无线网络中设计邻近图拓扑结构时,一般要考虑3个方面:•连通性(connectivity):通常是前提,也有例外,如2.16节介绍的k-Neigh结构.•局部性:构造邻近图所需知识范围越小,通讯负担也就越低,越能支持移动节点,网络可扩展性越强.•能耗有效性:可用dsf,hsf,psf(或其他参数)来衡量.通常与路由协议结合效果更佳.考虑到现阶段基于RF通讯的方式,为提高通信效率还需要注意生成图的:•稀疏性(sparseness):边连接密度不宜过大(通常|E|=Θ(N)),以降低MAC层干扰.•冗余(redundancy):节点的平均度或点对间的路径数不宜过低,否则导致数据传输路径延长,网络拥塞,吞吐量降低,容错能力[2]、可靠性差.880JournalofSoftware软件学报Vol.19,No.4,April2008•可平面(planarity):边的非顶点交叉现象将给信道带来干扰.•提高空间复用率:通常,小的邻节点度及低的传输半径有助于减轻隐藏终端和暴露终端问题的影响,有利于提高空间复用度,并降低设备成本提高可靠性.•其他.以上没有任何一条是绝对必须的,通常会根据应用场景,在这些因素中选择一个综合昀佳的平衡点.1.3邻近图结构的一种分类•平面型:节点在图结构中地位平等.本文第2.1~第2.16节介绍的邻近图结构均属此类.•层次型:如支配集DS(包括CDS,IDS)等,节点在图结构中处于不同的地位.第2.17节、第2.18节属此类.2邻近图结构综述点与其邻节点根据不同映射关系进行关联,产生了千差万别的邻近图结构.为方便阅读,依构造方式差异,我们按以下不严格的分类介绍文中平面型图结构:•几何位置约束型(简称几何型):直接以点与邻点的距离、角度做约束条件构建的图结构.第2.1节、第2.4~第2.8节属此类.其他类型的约束条件均可看做距离、角度等几何要素的函数.•组合型:将多种已知图结构的构造要素组合,形成新图.第2.9~第2.11节属此类.•昀优化型:将目标函数在约束条件下的解转换为几何要素而构造的邻近图结构.第2.2节、第2.3节(由于其重要性及方便后文引用而提前介绍)、第2.12~第2.15节属此类.这个类型中有一个可称做“MST优化型”的子类,它们实质是以特殊权值推广距离定义,因而都可由相同算法构造.第2.13节、第2.14节属此类.•概率型:依据某概型理论来选择邻节点连接.第2.16节属此类.除特别指出,都假定节点昀大通讯距离同为Rmax时,图能够构造;如果没有明确提到边的方向,则为无向边.2.1UDG(unitdiskgraph)当图定义在相同点集空间上时,UDG(或者还有DG,见下文)是所有已知、未知邻近图结构的发源地.定义.当且仅当u,v两点距离≤Rmax时,边(u,v)∈G.UDG还有一些等价定义,如所有节点发送半径相等;由等半径的圆组成,当且仅当一个圆包含另一圆的圆心时,两圆之间存在连接边.如果允许节点的昀大发送半径不同,则称DG(diskgraph).另外,有文献定义Rmax为1,本文用Rmax替代1更直观,实质无二.UDG中,n+=N−1,2maxnRλπ=•.UDG唯一、不一定可平面.2.2MST(minimumspanningtree)定义.UDG中包含所有N个节点的生成树,要求满足边代价之和昀小.构造算法:Prim和Kruskal方法已为众所周知,时间复杂度O(mlogN),这里,m表示边数,需要全局知识.如果已知DTG,则复杂度为Θ(N)[3],由于DTG本身需Θ(NlogN)