通信工程tang-译文.doc

通信工程tang-译文

移动Ad Hoc网络基于位置的组播路由协议

摘要：本文提出的是移动Ad Hoc网络基于位置的组播路由协议。一个网络根据地理位置信息分为网格，这些网格网络根据标签分为高通道子网和低频道子网，根据源节点把目的节点分为子集。然后目的地节点分割成使用位置信息的组，这种组播路由就是没一个标签组。拟议的议定书并不需要维持一个分布结构（例如，树状或网格）。一个转发节点只需使用关于其目的地和其邻居的位置信息便能决定下一次跳转的数据包转交，因此非常适合高度动态的网络。提出的协议具有可扩展性。

1、前言
移动Ad Hoc网络（ MANET网络）是自组、动态拓扑网络所形成的集合移动节点通过无线链路。许多应用中的移动ad hoc网络依赖组通信。通信救灾期间、网络游戏和车辆紧急警报网络都是这些应用程序常见的例子。因此，在移动通信Ad hoc网络中组播起着重要作用，并且这些年收到了极大地关注。一些组播协议的Ad Hoc网络已经提出，其中大多数是保持某种形式的分配结构以提供组播。它们大致可分为树为基础的协议和网格为基础的协议。树为基础的协议，比如AMRoute、MZR、ADMR和DRMR，只提供一个路径之间对源和接收器。合并的道路，形成了所有接收组播树。以网格为基础的方法，可能有多个路径之间发送和接收。这冗余提供更多的保护对拓扑变化。例如网格为基础的组播路由协议的移动Ad Hoc网络。基于位置的多播路由协议的移动Ad Hoc网络是DCMP、CAMP、NSMP和ODMRP。性能比较研究表明，树为基础的协议降低数据包投递率和更糟的综合性能优于网格为基础的移动环境。当一个多播组成员居住在一个特定领域时，了解地域位置的节点已用于改善ODMRP与移动预测和限制洪水。在动态源组播(DSM)，每个提供淹没网络的节点都提供自己的位置，因此每个节点都知道在Ad hoc网络中其他节点的位置。发送一个多播包然后通过所有接受器的位置信息构造一个组播树。此树一个封包的有效编码。基于组播的位置(PBM)是推广现有的单播路由算法。使用地理位置参与节点转发的数据包。关键是利用PBM规则分裂的多播数据包，和维修策略的情况下不存在任何直接的邻居，也是的取得一个或多个目的地的进展。PBM只包括多播数据包标题中所有目的地的地址，它没有战略的组织所有目的地并且选择邻居不仅取决于距离，可扩展性仍然开放问题。可扩展的组播被提议。

本文主要是介绍组播协议的被提议的，网络分为网格，采用拟议的议定书的位置信息进行分类的目的地设定，并在每个网格选择一个主机。这种网络结构成功地用于目的地节点集的整理，并直接传送多播数据包。
本文安排如下。第2节介绍了计划的建构性和标签分配的二维网格；第3节给出了位置为基础的单播路由协议；第4节中，我们提出了多播路由协议；第5节为结论，并提出了进一步的工作。
2、二维网格的建设和标签分配
假定每个节点了解自己的实际位置，也就是其精确的地理坐标，这可通过使用全球定位系统（ GPS ）和当时的节点，收到自己的位置。它将其位置信息发送到所有其他节点。
位置服务技术将被作为一个特殊的论文来讨论。如图1所示，MANET中的地理区域被分割成二维逻辑网格显示。1 ，每个平方米被称为一个网格区，每个网格是一个d × d正方形的大小，期中d是网格的边长设R是传播的无线电信号，对于d来说更小的值意味着网络中更多的网关，而这又意味着更高的费用提供更多的数据包和广播风暴。如果d太大，无线电信号网关主机将难以达到网格以外的的地方，从而网关到网关的通信是不可能取得成功。d的值涉与到r和路由协议。本文图2我们确定d和r的关系为。2，保证一个主机已达到任何相邻的东八区主机。这是方便的选择在一个网格的网关。

图1，逻辑网格划分物理领域

图2，无线电信号一个网格r和边长d的传播关系
在本节中，我们将提出一个标签任务计划的网格拓扑，并证明该任务计划将提供单播路由网格中来源和目的节点间跳跃的最短路径。假设一个在二维网格中地址为整数坐标为（x，y），左下角为（0，0）。每个网格分配一个为l（u）的标签。标签赋值函数l表示为一个m×n的网格区域。x，y坐标网格如下：

y是偶数

y是奇数

在图1中的每个逻辑网格都标有一个l(u)的标签。图3展示了一个6×5的网格区域，在每个网格所代表的一个整数，我们可以认为每一个网格可以与八个邻居直接连接，标签有效地把一个网格网络分成两个子网。高通道子网被用于沟通低标网（网关）到高标网（网关），例子如图4（a）；地通道子网络可以用作在高标网（网关） 到低标网（网关）的传输，如图4（b）。组播通信将使用邮件路由的标签。如果标签的目的地区大于其源区标签，组播路由总是发生在高通道子网，否则，它将采取低频道子网。

图3，6 × 5网格网络的标签

（a）高通道子网 （b）低通道子网
图4，在6 × 5网格网络中的高频道和低频道子网

3、单播路由协议
设计一个路由协议应考虑三个主要问题：路由发现、分组中继和路由维护。在路由发现中，位置信息用来确定路由的质量。Ad Hoc网络中的一个节点从一个系统如全球定位系统（GPS）中获得其位置。在位置不知道的协议中，路由发现由盲目的泛洪式搜索完成，这很容易导致广播风暴问题。[7]中基于位置的组播方案用转发区域来避免网络范围的泛式搜索，因为它的转发区域太广，在一个转发区域内可能存在大量不必要的泛式搜索数据包，且当一个数据源达不到它的目的地时，它无法给出如何选择中继主机的方案。本文将解决这个问题。我们假设一个数据节点知道它全部目的地的位置。定位服务我们将在另一片文章中进行特殊的讨论。一个数据节点将一个数据包传向一个邻近的节点，此节点靠近其目的节点。一个数据源的位置与其目的地被用来限制转发范围。当达到一个目的节点时，一个相同的过程将会重复进行。
在单一路由协议中，路由通过网格网关用网格到网格的方式运行。如果一个网关脱离原来的网格，一种类似于蜂窝系统中的“越区切换”程序的行为将会发生。在这种情况下，一个网关将其路由信息传送到下一个网关。每个网关在它的网格区域保持了其节点信息，且有一个规则来决定节点将传送数据到哪个网格。只有本地信息，而非全球性的信息，用来转发数据包。在我们的协议设计中，我们将考虑两个问题，一个是在信息路由的每个步骤中尽可能少的节点被搜索到，另一个是路由路径竟可能短。
我们假定每个数据源节点能够通过定位服务机制得到其目的地的位置。因此，到转换区域的一个路线可以由发送端的位置和目的地的坐标来确定。我们将两个网格间的距离定义为：，， 。通过当前网格的邻居网格与目的节点所在的网格之间的距离来选取一个转换转换网格，然后选择与目的网格距离最短的网格作为一个转换网格。
令V是一个网络中所有网格的集合。寻找一个2D网格的无死锁的单播算法就是定义一个路由函数：，在这种方式中它运用了两个子网来避免循环路由。这里，两个网格和是相邻的，例如， 。有一个这样的路由函数：一个数据源节点在网格，目的节点在网格，定义，则是的一个邻近网格，且如果，我们有如下等式：
，否则，如果，我们有如下等式：
。
如果有更多的主机满足条件，我们只有全部选取。

（a）数据源1，目的地28 （b）数据源23，目的地6
图5：在网格的高通道和低通道子网中的单播路由
单播通信用标签作为路由。图5展示了高通道子网和低通道子网中的单播路由。图5（a）给出了在高通道子网中从网格s（）的一个数据源主机到网格d（）的目的主机的所有可能路线，其中所有的路线都只是从低标签网格的主机到高标签网格的主机；图5（b）给出了在低通道子网中从网格s（）的一个数据源主机到网格d（）的目的主机的所有可能路线，其中所有的路线都只是从高标签网格的主机到低标签网格的主机。在每步中数据包将一个中继点转发到最接近其目的地的位置，在网格水平上数据源与其目的地间的路线遵循最短路径。
4、组播路由协议
对于从源节点S到目标节点集D的组播路由，其算法有两部分组成：信息编制和路由。第一部分将一个信息的目标集合在两步中分为多个子集。第一步，节点S生成的信息的目标集合被分为两个子集和，包含所有目标节点网格高于网格S的值，包含所有目标节点低于网格S的值。运用它们的网格标签作为一个关键点，将中的目标节点按递增次序分类。对也做同样的处理，但按照递减的次序。第二步，目标集合和被分别分为更多的组，这些组取决于和相应目标节点间的网格的距离。第二部分决定了信息的路径直至每组的所有目标节点都达到。路由通过运用单播路由协议每组中标签的顺序来完成。为了叙述的简洁明了，其中的网格和节点用同一标签标示，两个节点间的距离意味着两个节点分别所在的网格间的距离。

算法1。组播路由从S到目的地设定为DH（或DL）
1，让节点为dn,n=1,2,...为DH的第n个节点，并以升序排列（或在DL中以降序排列）。如果d(d1,d2)>d(S,d2)，那么d1，d2在不同的组，否则d1，d2在同一组。
2，假设在DH（或DL）的前n节点已被分成不同的组Gi，1≤i≤k，并让gi节点为Gi的最大序列号（或最小序列号），如果d（dn+1，gi）>d（dn+1，S），其中1≤i≤k，则dn+1在新组且k+1=>k，否则dn+1属于，d(dn+1,gm)=min{d(dn+1,gi)|1≤i≤k}且n+1=>n。
3，如果n<|DH|(or n<|DL|)，参考2
4，S 以单播路由算法发往Gi第一个节点的数据包，1≤i≤k
5，对于每个平行的Gi，让|Gi|=ki,gj∈Gi,1≤j≤ki对于j=1到
用单播路由算法发送数据包从到

在这里，我们将讨论算法1的时间复杂度，我们把|DH|设为目的节点，在第1步，我们需要时间常数O(1)；第2步复杂时间为k，这里的k为租的数量且k≤|DH|。第2步和第3步会重复DH时间最多次。所以|DH|=n1，第2步复杂的时间和第3步算法1中。时间复杂度的排序DH是总时间复杂度的部分目的地节点DH为。在第4，5步中任何单播路由间的跳跃为不超过直径为d的网络，所以第4，5步中时间复杂度为O(dn1)。算法1中总时间复杂度到目的地DH为O(n1(d+n1))。如果|DL|=n2，则算法1中的总时间复杂度到DL为O(n2(d+n2))。
提出的组播路由算法的性能取决于目标节点的位置分布。为了减少2D网格中的时间成本，终端集合和可被进一步分块。集合可被分为两个集合，一个集合包含了坐标大于或等于源节点S坐标的所有节点，另一个集合则包含了剩余的节点。采用相同的方法来划分。算法1被同时用于四个子集，时间的复杂程度则可以降低。

目的地节点升序排列，并为目的地的每组设置DH，降序排列每组设定DL，邮件路由使用每组中每一对连续的目的地节点的单播协议。组播路由路径图如图7所示

源节点的网格

目的节点的网格

图6。把分区目的地划分为6×5网格不同组的例子

源节点的网格

目的节点的网格

图7.多播路由作为6×5网格的不同组

5、结论
在本文中，我们对移动ad hoc网络提出了一种组播路由模式。新的路由方案基于主机的地理位置信息，首先，一个网络被分为一个个网格，网格网络则根据网格的标签分为高通道子网和低通道子网。第二，一个目标的集合根据其源节点可分割为两个子集，每个集合的目标节点分为不同的组，在此之后，没组的组播路由按标签顺序来完成。被提出的协议不要求分配结构的维持（如网格树）。一个转发节点仅需运用目标与其邻居的位置就可决定下一个中继段，这个中继段由一个数据包转换而来且非常适合高度动态的网络。被提出的协议是可扩展的。运用NS-2模拟器对提出的协议进行仿真模拟，其运行状况良好。我们将进一步研究组播路由的稳定性。

11 / 11