关键字 |
| ALBA-R，凸壳，GDSTR, LDSTR，贪婪壳，生成树 |
介绍 |
| 在地理路由中，每个节点都可以确定自己的位置，并且源节点知道目标节点的位置。有了这些信息，消息就可以被路由到目的地，而不需要知道网络拓扑结构或预先发现路由。在某些路由算法中，路由选择是通过将多个度量组合在一个度量中进行选择来完成的。在各种地理路由协议中，采用多种路由度量来实现高效的路由。本文指出了现有的路由协议存在的一些问题:贪婪路由协议简单，不提供传输保证;MFF路由协议提供了传输保证，但复杂，可能产生非常低效的路径;最后，平面化成本和位置信息不可用是地理路由部署中的主要问题。为了在位置信息不可用的情况下实现良好的地理路由协调，实现了多个与地理路由相关的协议。GDSTR (Greedy Distributed Spanning Tree Routing，贪婪分布式生成树路由)是指当报文在贪婪转发过程中陷入死胡同时，从平面图切换到生成树上进行路由。为了在树上选择最有可能朝着目的地前进的方向，每个GDSTR节点使用凸包维护每个树邻居下面的子树所覆盖区域的摘要。这种分布式数据结构称为船体树。GDSTR不仅需要一个数量级的带宽来维护这些船体树，而且它通常比其他基于平面化的地理路由算法获得更好的路由性能。 |
相关工作 |
| H. Takagi等人(1984)[2]在本文中采用终端随机分布的多跳分组无线网络，通过各种传输协议和网络配置来确定数据包在期望方向上的期望进度最大化的最优传输半径。B.N. Clarket等人，(1990)[3]这篇论文单位盘图是平面上等大小圆的交图:它们为广播网络(蜂窝网络)和计算几何中的一些问题提供了一个图论模型。E. Kranakis et al.，(1999)[5]提出了一种路由算法，称为局部路由算法，用于查找起点和目的地的位置。P. Bose et al.，[6]在本文中，无线网络路由问题被建模为单元图，其中节点是平面上的点，如果两个节点之间的距离小于某个固定单元，它们就可以通信。K. Seada等，[7]在本文中没有位置误差，使用贪婪转发和面路由相结合的地理路由已被证明是正确有效的工作。Y.-J。Kim et al.(2005)的论文地理路由被广泛认为是最有前途的一般可扩展无线路由方法。然而，目前提出的所有地理路由算法的正确性依赖于对无线电及其产生的连通性图的理想化假设。Q. Fang et al.，(2006)在实际的传感器网络部署中，传感器的空间分布通常远远不是均匀的[8]。P. Casari et al.，(2007)[6]在本文中无线传感器网络(WSN)中的地理转发一直存在绕过“死角”的问题，“死角”是指网络中在数据收集点(接收器)方向上找不到节点的区域。 Z. Li, R. Li, Y. Wei (2010) Localization is one of the key techniques in wireless sensor network. The location estimation methods can be classified into target/source localization and node self-localization. In target localization, mainly introduce the energy-based method. [4]A. Camillo et al., (2013) presents IRIS, an integrated interest dissemination and convergecasting solution for wireless sensor networks (WSNs). The interest dissemination protocol is used to build and maintain the network topology and for task/instruction assignment.[5] S. Ruhrup et al., (2013) in this paper beaconless or contention-based geographic routing algorithms forward packet towards a geographical destination reactively without the knowledge of the neighborhood.[9] Such algorithms allow greedy forwarding. Anandhi.R, R.Manicka chezian(2014) presents an Overview of geographic routing protocols in wireless sensor network. In WSN, the state required to be maintained is minimum and low overhead, in addition to their fast response to dynamics. [1] |
GDSTR概述 |
| 贪婪分布式生成树路由(GDSTR)描述了用于路由的船体树，以及如何构建和维护它们。它还描述了如何使用船体树来实现地理广播和近似路由，以及改进的GDSTR, GDSTR的变体，为具有小空隙的密集网络实现优越的路由性能。与之前的地理面路由算法一样，GDSTR尽可能使用简单的贪婪转发来转发数据包。在生成树上切换为转发模式，只对绕过void的报文进行路由，避免局部最小值。[11]一旦可行，它就会切换回贪婪转发。GDSTR能够保证数据包在一个连通的网络中传递的原因是，树遍历转发方式可以保证将数据包传递到网络中的任何节点，而不需要贪婪转发。 |
| 生成树包含网络中的所有n个节点，通过类似于深度优先搜索的方式遍历树，我们可以成功地将数据包传递到网络中的任何节点。这种遍历不需要在包中存储状态，并保证包将在不超过2n - 3跳的情况下交付。如果指定的目的地没有在树中找到，如果在包中存储了关于开始节点的信息，那么我们可以在2n - 2跳内终止遍历。所提出的工作的一个主要贡献是定义了一种新的分布式数据结构，一种我们称为船体树的增强生成树，它允许将上述搜索问题限制到给定目的地的全生成树的一个小子树，从而保证包传递的时间远远少于2n - 3跳。 |
船体的树木 |
| 壳树是一种生成树，其中每个节点都有一个相关联的凸壳，凸壳包含其所有后代节点的位置。船体树提供了一种聚合位置信息的方法，它们是通过在树中聚合凸船体信息来构建的。该信息用于路由，以避免没有生产力的路径;相反，我们遍历一个显著减少的子树，只由包含目标点。[12]的凸包节点组成 |
| 基本壳树中的每个节点存储关于凸壳的信息，其中包含与图1中指定的每个子节点相关联的子树中的所有节点的坐标。凸包信息在树上聚合。每个节点根据其坐标和所有子节点的凸包上的点的并集计算其凸包，并将此信息传递给父节点。因此，与根节点相关联的凸包是整个网络的凸包，包含了网络中的所有节点。 |
生成树构造 |
| 通过对多种生成树算法的评价，发现最小深度树的路由性能最好。最小深度树的构造方法是让每个节点选择到根的跳数最少的邻居作为父节点。当一个节点在多个距离根节点跳数相同的相邻节点之间进行选择时，优先选择最近的节点。[13] |
| 事后来看，最小深度树产生最佳路由性能并不奇怪。首先，最小深度树倾向于优先选择较短的链接。参考图2中的示例，应该清楚地看到，较短的链接减少了交叉链接的发生。 |
| 空隙中最靠近根的区域称为上树区域。在这个区域，空洞的边缘不是船体树的边缘，因此围绕这个区域的路由涉及到树的上下路由。对于空白的其余部分，所有的边(除了一条)都是最小深度树的一部分。因为最小深度树会生成每个节点与其所有祖先节点之间的最短路径，所以沿着这些区域的树遍历是有效的。因为生成树不包含循环，但必须包含网络中的所有节点，所以在距离根的空隙的远端，只有一条边不是树中的边。我们称之为缺失的环节。这条缺失的边限制了包在使用船体树的空隙中只能向一个方向转发。给定两棵船体树，我们观察到，只要这两棵树不共享相同的缺失环节，它们就会一起允许沿两个方向(顺时针和逆时针)绕着空洞穿越。为了增加生成覆盖空隙不相交区域的船体树的概率，一种方法是将它们的根设置在网络的两端。 |
提出GDSTR |
| GDSTR适用于具有较大空隙的稀疏网络。对于密集网络，地理面路由算法可以获得更好的性能，因为其空洞趋于较小，且通常选择哪个转发方向无关紧要。这是因为当船体树的根和叶子之间有很多跳时，船体树不能像平面面那样近似空洞，因此GDSTR会引起额外的路由开销。此外，当船体树较大时，预计geocast的效率较低。 |
| 一种可能的方法是在稀疏网络中使用GDSTR，在中等密度网络中使用地理面路由算法。然而，这种方法并不能解决平面化网络图的高维护成本。另一个问题是，大型网络可能是异构的，有一些密集区域和一些稀疏区域。理想情况下，一个好的地理路由算法应该在所有密度的网络中都能很好地工作。所提出的系统改进了GDSTR，这是GDSTR的一个变体，它集成了本地信息，以提高密集网络中的路由和地理广播性能。 |
| 概述: |
| 改进LGDSTR的关键思想是用两个本地树森林和一个额外的贪婪船体转发模式来增强GDSTR。在LGDSTR中，节点将首先尝试像以前一样贪婪地转发数据包。当贪婪转发失败时，利用局部壳树的凸壳中包含的信息切换到新的贪婪壳转发模式。所谓局部，是指树只包含有限局部的节点。由于不能保证正确性，只描述转发。 |
| 使用本地树有时会失败，在这种情况下，节点将切换到两个原始全局船体树中的一个进行转发，这是保证成功的。为了实现贪婪壳转发，局部壳树采用了不同于GDSTR的凸壳聚合算法来维护全局壳树。这种新的聚合机制提供了一个节点，该节点具有可通过每个相邻节点访问的位置视图。为了以这种方式聚合船体，每个节点广播所有邻居的船体，而不是自己的船体。用图3所示的示例说明局部船体树聚合算法。特别是，与每个邻居相关联的凸包包含通过该邻居可到达的目标点集。在本例中，节点n1和n2都有三个相邻节点。在图3(a)中，显示n1视角下的凸包。在这个新方案下，n2的keepalive消息将包含n1, n5和n6的车体。从n1的角度看，n2的凸包是包含n2的凸包以及n5和n6的凸包。 |
| 在图3(b)中，从n2的角度来看，n1的凸包是包含n1的凸包以及n3和n4的凸包。这为每个节点提供了可以通过树中的每个相邻节点访问的地理坐标视图。在图4中，节点s接收到目的地为t的数据包，必须决定如何转发该数据包。由于节点s是贪婪转发的死胡同，所以它尝试采用贪婪壳转发方式转发报文。在该模式下，节点s考虑相邻节点的凸包，在凸包中找到离目标t最近的点，即节点n2的凸包上的点r。因此，节点s将数据包转发到n2而不是n1。与GDSTR一样，报文切换到贪婪壳转发模式的节点坐标记为nmin，一旦报文切换到贪婪模式，报文就会恢复到贪婪转发模式。在前一种情况下，数据包将在两个可用的全局树之一上切换到GDSTR树遍历模式。pull只使用单调地更接近目的地的值进行更新。如果处于贪婪转发模式的数据包最终进入死胡同，并且相关节点没有一个凸包，凸包的点更接近于拉点，则数据包将绕过贪婪壳转发模式，直接切换到两个全局树中的一个上进行树遍历。 This is to prevent oscillations. |
| B.本地树gdstr: |
| 为了构建局部船体树，将坐标空间划分为一个固定长度的方格网格，每个方格中的所有节点都是同一局部树的成员。局部树的根是坐标最接近网格方块中心的节点。构建这种树的过程有两个步骤:首先，节点试图将数据包路由到其本地网格方块的中心。这样做将允许它识别其本地树的根节点。接下来，它通过将包路由到根节点来确定它的父节点。第二步是必要的，因为给定的节点可能没有通过同一网格正方形内的邻居连接到其船体树的根。图5(a)所示的示例说明了这一点。在这个例子中，节点r是局部船体树的根，因为它离正方形网格的中心最近;然而，节点连接到正方形网格外的邻居。。得到的局部车体树如图5 (b)所示。这个例子还表明，靠近网格方块边缘的节点可能是相邻网格方块局部车体树的成员。 The strict membership condition imposed that all the nodes within each grid square belong to the same local hull tree to provide correctness guarantees for geocast. |
绩效评估 |
| 本文的目标是比较LGDSTR与其他地理路由算法的基本算法行为。路由性能是根据两个指标来衡量的:i)路径拉伸ii)跳拉伸路径拉伸是两个节点之间的总路径长度与最短路径(欧氏距离)的比率;跳长是两个节点之间路由的跳数与最短路径的跳数之比(以跳数表示)。绩效评估的衡量标准是: |
| 1)网络密度效应2)网络规模效应3)障碍的影响。通常，GDSTR只使用两个全局船体树。为了理解两者之间的权衡，我们比较了具有一棵和两棵局部树(以及两棵全局树)的LGDSTR的性能与具有两到四棵全局船体树的GDSTR的性能，以确定具有三棵或四棵全局树的GDSTR的性能是否相同。 |
| 特别地，我们看到LGDSTR实现了比GDSTR和ALBA-R更好的路由性能。LGDSTR能够超过GDSTR和LGDSTR的路由性能。对于500节点网络，具有两个局部船体树的LGDSTR比具有两个全局船体树的GDSTR在拉伸上提高了17%，比ALBA-R低了8%。 |
| 最后，对于具有小空隙的密集网络，LGDSTR能够实现比GDSTR提高17%的拉伸性能，比现有最好的人脸路由算法ALBA-R降低8%的拉伸性能。我们还展示了，与GDSTR(有两个船体树)相比，我们可以用LGDSTR船体树少10%的开销实现地理cast。此外，对于规模小于500个节点的网络，我们的算法可能需要不超过最小消息数量的两倍。 |
结论 |
| 本文解释了LGDSTR在跃点拉伸和路径拉伸指标上的性能改进。该算法比GDSTR和ALBA-R等其他路由算法效率更高。地理路由的基本原理是，节点相对于数据包目的地的物理位置提供了正确的一般转发方向的良好提示。虽然LGDSTR目前是在三维笛卡尔坐标上实现的，但它可以推广到高维空间中的坐标，因为凸包专门用于高维。最后，LGDSTR可以在高维空间中实现更好的路由延伸。局部GDSTR实现的挑战是在3D中降低局部最小值，保证数据包传递，跳延伸接近1,Out在性能和成本上都表现为2D，可扩展到500节点的网络。 |
|
表格一览 |
 |
|
| 表1 |
表2 |
|
|
数字一览 |
|
|
|
参考文献 |
- Anandhi。R， r.m anicka chezian博士，” A Review on Geographic Routing in Wireless Sensor Network,” International Journal of Innovative Research in Computer and Communication Engineering, Vol. 2, Issue 7, July 2014, pp. 5101-5106
- L. Barrie’re, P. Fraigniaud, L. Narayanan，和J. Opatrny，“具有不稳定传输范围的无线Ad Hoc网络中基于位置的鲁棒路由”，J.无线通信和移动计算，第2卷，第2期。3, pp. 141-153, 2001。
- S. Basagni, M. Nati，和C. Petrioli，“无线传感器网络的定位错误弹性地理路由”，IEEE GLOBECOM，第1-6页，11月/ 12月。2008.
- P. Bose, P. Morin, I. Stojmenovic和J. Urrutia，“Ad Hoc无线网络中保证交付的路由”，ACM/ Kluwer无线网络，第7卷，no. 1。6，第609-616页，2001年11月。
- A. Camillo '， M. Nati, C. Petrioli, M. Rossi和M. Zorzi，“IRIS:无线传感器网络的集成数据收集和兴趣传播系统”，Ad Hoc网络，Ad Hoc和传感器网络的跨层设计特刊，第11卷，no. 1。2, pp. 654-671, 2013年3月。
- B.N. Clark, C.J. Colbourn和D.S. Johnson，“单位盘图”，离散数学。， vol. 86, pp. 165-167, 1990。
- P. Casari, M. Nati, C. Petrioli和M. Zorzi，“在稀疏拓扑中使用随机转发绕过死角的高效非平面路由”，Proc IEEE国际会议通信(ICC ' 07)，第3122-3129页，2007年6月。
- 高，L.J. gu, J. Hershberger, L. Zhang，和A. Zhu，“移动网络的几何扳手”，IEEE J.通信选择领域，第23卷，no. 1。1，页174-185,2005年1月。
- E. Kranakis, H. Singh，和J. Urrutia，“几何网络上的罗盘路由”，第11届加拿大会议，计算几何，第51-54页，1999年8月。
- K. Moaveninejad, W. Song，和X. Li，“无线Ad Hoc网络的鲁棒基于位置的路由”，Elsevier Ad Hoc网络，第3卷，no. 3。5，页546-559,2005年9月。
- S. Ru¨hrup和I. Stojmenovic，“无线传感器网络中保证传输的无信标定位优化通信开销，同时减少路径长度”，IEEE传输。计算机，第62卷，第1期。12, pp 2240-2253, 2013年12月。
- K. Seada, A. Helmy，和R. Govindan，“传感器网络中定位错误对地理面路由的影响”，IEEE/ACM第三届国际会议。传感器网络中的信息处理(IPSN’04)，第71-80页，2004年4月。
- I. Stojmenovic，“Ad Hoc网络中基于位置的路由”，IEEE通信杂志，第40卷，no. 1。7，第128-134页，2002年7月。
- H. Takagi和L. Kleinrock，“随机分布分组无线电终端的最佳传输范围”，IEEE Trans。通讯，第32卷，no。3页246-257,1984年3月。
- M. Zorzi，“在Ad Hoc和传感器网络中用于地理转发的一种新的基于争用的MAC协议”，Proc。《IEEE国际会议通讯》(ICC’04)，第6卷，第3481-3485页，2004年6月。
|
菜单
