基于树的广播

概要

虽然基于树结构的广播在网络中已经被熟知是广泛的被应用的技术，它通常被认为不适合ad hoc网络，被维护的树对网络变化非常敏感。相反，这篇论文提出了一个基于广播模式的有效树，即使在AD hoc网络的网络结构不断变化的情况下，也能保持可靠和稳定。

为了实现这个，首先一个新颖的方法被踢出来维护完全分布式ad hoc网络中的生成，使用异步和在线的方式。一旦建立了树，广播本身就会基于树执行。本文还提出了对基本算法的进一步改进，以进一步减少资源需求，增加树的可靠性，允许允许考虑节点的移动性，并使方法更加具可配置性。

就如同在模拟中展示的，得到的广播方案是稳定的，可靠的，它使用小的资源开销：广播树的无环结构保证了节点只会得到信息一次，因此广播所需的带宽很少，节点不需要存储最近的广播消息，减少了计算和内存需要。

作为一种副产品，提出了一种测量节点迁移率的技术。这个技术需要添加GPS设备或者地理信息，但是它是基于节点的链路稳定性的。

1 介绍

移动ad hoc网络（MANET）是一个交流网络的形式，通过移动无线电设备（如笔记本，pad）而不需要固定的基础设施，每个通信设备（以下简称节点）可以作为其他通信设备的路由器。manet对于用于操作它们的通信协议提出了许多挑战。第一也是最重要的，协议需要考虑到节点移动而导致的网络拓扑结构的变化，在大多数应用程序中，协议应该使用完全分布式的算法，因为由于缺乏固定的基础设施，没有中心实体可用。另一方面，通过空中接口的通信应该保持在最低开销，它通常是在这些网络中的稀缺资源，由于大多数节点使用有限的电池的手段设备，因此能量消耗必须最小化。

目前的工作重点是全网的广播，这是将一个信息传递给所有节点的过程。针对ad hoc网络中的广播提出了一种新的解决方案。这个思想是在网络中维护生成树，不是吧广播消息转发给所有令居，而是转发给树中的邻居。因为树是无循环的，每个节点接受一次消息，与现有方法比有俩个优点。首先，不需要存储之前的广播，以避免广播消息在链接循环中无休止地大量增加。只有广播的始发节点才需要存储该消息，如果消息非常重要，则需要关注消息是否广播成功。考虑到广播消息需要转发多少次，这是非常经济的。假设广播树处于稳定状态，在一对一广播转发的情况下，每个节点只转发一次广播消息。如果本地广播可用，则广播消息的转发次数应该与广播树中非叶子节点数量一样多。

广播和多播在网络中使用树不是什么颖欣的注意。在文献中也可以找到一些针对于网络中生成树的自动化和分布式构建算法（见 2.4章）。然而如同上文中提到的应用在ad hoc网络中添加了特别的要求。也就是说，没有节点知道整个网络的结构，只知道它们的直接邻居。因此，节点之间需要通过连通性来构建生成树。当然我们需要劲量减少这种交流。算法需要用一种方式处理每个节点，来避免整个网络依赖于一个或多个专用节点的可达性。我们还希望最小化每个节点在树计算期间和之后存储的数据结构。最重要的是这个算法需要能够应对网络拓扑的持续改变。时不时的链接出现和消失。破坏树或者链接俩个之前断开的网络。树算法需要立即反应这些改变。

事实上，由于这个强需求，基于树的广播广泛被认为不适用于ad hoc网络，维护起来过于困难和消耗资源（连通性和无环属性都不是本地特征）并且对链路的故障过于敏感。

相反，作为主要贡献，这篇论文提出了新的生成树算法来应对以上需求。提出的TreeCast方法是完全分布式和完全去中心化的。他不需要专用的节点或者任何长度leader选举过程。每个节点完全相同（非常简单）处理。它是异步的，也就是说节点不需要公共计时器。每个节点只知道它的直接邻居。没有其他的关于实际网络的信息需要。

TreeCast算法是在线，每当出现新节点或俩个分离的本地网络由于出现新的链路而连接起来时，该算法自动扩展树，当树因链接停止而破裂时，它将会自动修复树。算法同时处理建立和停止的路，即便网络结构发生重大变化时，它能迅速稳定。它只需要一点沟通和计算资源量就能工作。

TreeCast算法还能考虑节点的移动性。给出了一种基于节点连接稳定性来度量属性的方法。此外，算法不缺规定一些节点是树中的叶子节点，有必要防止节点在广播上花费大量资源。

一旦构建了生成树，广播机制就十分简单了，就像3.2章中一样。

在网络修改十分频繁的例子中，被提出的生成树算法可能会微调来增加树的稳定性（即介绍达到稳定状态的事件需要，即便是在网络发生根本性的变化之后）并且进一步减少所需要的交流。第4节为此目的提出了一些改进。第4.3节描述了拟议的流动性措施。在第5节进行了一些讨论之后，第6节给出了该算法在实际条件下的性能的数值结果。最后在第7节得出结论。

2 state of the art

网络范围的广播有俩个主要用处，即控制信息的传播和用户数据的传播。根据这个划分我们可以对这俩种类型的传播制定不同类型的需求。

用户数据广播通产更需要一定程度的可靠性。这是因为应用级别的回复从每个对等节点，这是因为来自所有对等节点的应用程序级确认会不必要的增加网络负担。这些网络算法通过底层的路由算法（单播）一些时候可以从路由信息聚合中获益。因为这些广播事件很少并且它们构成了用户流量，因此在资源使用方面相当昂贵。

控制数据广播在另一方面通常需要较少的可靠性。广域网广播在MANET路由协议中最广泛的应用是传播路由查询类型的报文。在大部分情况下广播达到单个及诶单就足够了，该节点知道查询中节点ID的位置。因此要求广播不应该系统的离开一些节点或者网络的部分。通常这些广播算法依赖非常小的可靠性和拓扑信息。而且它们可能非常频繁（例如每次联系一个先前位置的节点时路由查询）它们组成控制流量。因此资源利用必须控制在最低限度。

MANET 是 "Mobile Ad hoc NETwork" 的缩写，中文通常称为“移动自组织网络”或“移动adhoc网络”。这是一种无线网络架构，由一组自主移动的设备（如智能手机、笔记本电脑或其他无线设备）组成，这些设备能够在没有固定基础设施（如路由器或基站）的情况下相互通信。

全网范围的广播机制通常依赖于可用的本地广播。这是通过发送信息给所有节点以进一步分发的机制。比如无线接口 即IEEEE802.11b大部分这是最流行的无线网络无线接口。如果没有本地广播是可用的，那么所有节点一对一发送消息到它所有的邻居节点（或者它的子集）。要注意一点，本地广播总是不会答复的，并且会因为它们的冲突导致丢失，因此可靠性远不如点对点消息分发。

[10]表明，以全分布式、低能耗、移动感知的方式实现全网广播并不是一项简单的任务。

2.1 泛洪

在MANET中实现网络尺度的广播的当前方法叫做泛洪（或者传统泛洪）[12]。在这个过程中，接受广播信息的每个副本首先检查它是否已经被收到过了。如果是，消息被静默丢弃。如果消息第一次被接受到，那么泛洪给他的邻居。

在[10]它展示了传统的泛洪算法有几个缺点。首先在无线接口使用和能源消耗方面相当昂贵。这是因为每个节点接受来自每个令居的广播信息（在这个例子中）虽然理论上一次接受就足够了。

第二，泛洪不可靠。这是因为，相邻节点试图同时使用不可靠的本地广播。因此碰撞可能会发生，且大多数情况都不会被注意到。因此，多次传输可能会有相反的效果，导致总广播信息的丢失。

2.2 基于拓扑知识的解决方案

一些网络尺度的广播算法[5,8,16]是基于每个节点有一些网络拓扑非本地的信息。通常假设某个小整数节点k跳的邻居的连通性是已知的。该算法利用这部分知识来减少中继广播消息的节点数量。

[8]的作者提出了俩个相关的解决方案 self Pruning和Dominantpruning。在第一种情况下，每个节点根据自己的邻居和发送节点的邻居的只是来决定是否应该不转发和广播消息（在这个方案中邻居节点在被发送消息中包括）。第二个算法建立在每个节点n知道它俩跳的节点上，计算和转发邻居集合。节点被选择到这个集合中，这样它们就覆盖了n的整个俩跳邻居。在转发广播消息n时，也与转发集通信，只有包含在其中的节点才会转发消息。在[16]中LENWB算法被提出，其中每个节点根据俩跳邻居的只是以及第一跳和第二跳邻居的程度来计算是否应该转发消息。在本地广播可靠的情况下，该算法是可靠的。

网络draft提出了广播决议协议，作为区域路由协议框架的一部分。算法构建了路由区域的概念（每个节点的k>=2跳的邻居），在每个区域内任意广播，转发边界节点（n的k跳邻居的子集），并且完全了解n的2k跳的邻居的拓扑。这些解决方案要求节点获取和存储关于网络拓扑或地理结构的大量信息。在非局部拓扑的只是的方法中，及诶单必须存储并更新器2、3或4跳领域

2.3 基于地理位置的解决方案

另一组算法[10,15]假设每个节点在网络中都配备了GPS设备。节点将自己的位置传递给相邻的节点，节点奖自己的地理位置传递给相邻的及诶单，录用这种地理位置信息减少转发节点的数量。

在b[10]中，作者提出了两种利用地理数据的方案。第一个（基于距离的模式）只有节点的距离（相对于无线电覆盖区域的半径）被使用，而基于位置的模型假设，所有节点知道邻居节点的地理位置。在这俩种情况下，每个节点根据预期额外覆盖区域的大小来决定是否转发广播数据包。

[15]的基于内部节点的广播算法假设每个及诶单都知道所有邻居的地理坐标以及其度数，有了这些只是每个节点确定在广播方面是否是内部节点。只有内部节点转发广播消息。

基于转却位置节点的方案需要额外的GPS硬件组件，这是有些昂贵而且不切实际的对于一些无线设备来说，比如无线鼠标，键盘或者耳机。为什么每个人都需要同时携带4-5个GPS设备呢？（一个在他的笔记本里，另一个在他的手机、耳机、掌上电脑或相机里。）此外这些方法假设仅从节点的位置就可以估计可见性，即主要取决于节点的距离。只有没有遮蔽物的情况下，即用户处于一片开阔地带的时候才是现实的。

2.4 树的创建和维护算法

上述方法还有一个共同的缺点，节点要存储广播消息，以便仅对每个消息的第一次接受做出反应。否则消息可能会在网络中多倍增加。避免消息接受多次最明显的方法是在链路的非循环子集上转发广播的消息，即在树上。在电信网络中有几种用于维护树结构的算法，比如生成树算法和桥接以太网[6]。不行的是大部分的这些算法被设计在稳定的网络中工作，而不是在不断变化拓扑结构的特定环境。

有一项重要的工作是处理组播树[1 - 3,9,17]，更具体地说，是处理ad hoc网络中的组播树（例如b[13]）。然而这些算法通常在预先存在的路由体系结构上维护几个相当稀疏的树。在目前的工作中，我们的重点是广播主要的控制信息，这意味着一个树跨越所有的网络构建没有事先单播路由数据。

用于广泛研究的领导者选举问题，例如[7]，通常生成生成树作为副产品。此外， 即便是最小代价生成树，也可以通过高效的分布式算法找到[4]。然而这些算法只处理树的构造，而不处理结构改变。[18]中提出的算法还隐含地涉及到生成树的构造。虽然该算法是为无线自组织上下文设计的，但它不适合树的维护。

确实一些ad hoc路由协议它们以来与底层的树或者森林拓扑。DST协议[14]维护生成树，并使用生成树来转发数据包，然而在对于树的维护方面（比如树的合并）涉及集中决策和广泛的信令。DDR[11]在令一方面使用了动态维护森林。尽管作者证明了它们的算法总是在一步中产生一个森林，他们甚至不打算为网络构建一棵树。此外协议在不可靠环境（例如可能丢失信标）中的性能也值得怀疑。

3 树广播算法

这一章节提出了一个有效的沟通算法以维护生成树和基于生成树的广播算法。如我们上问题到的，完全广播机制包括俩个任务：广播树的维护和广播进程本身。

3.1广播树的维护

每个节点有独立的ID参考也就是NodeID。NodeID应该是有序的，即NodeID应该是可比较的。例如，IP地址符合这个特性。

每个节点属于单个广播树。这个树也有ID叫做TreeID。一个TreeID是一对整数序列号，NodeID通过算法生成。节点的NodeId与其TreeID中的NodeID通常是不同的。

比大小的时候相比TreeID然后是NodeID，NodeID可以视为IP地址。

TreeID是字典序的，即它们也是可以比较的，比较的定义如下。如果序列号是不同的，那么有较大TreeID被定义为更大。如果序列号是相同的，那么具有较大NodeId的TreeID被定义为较大。

除了TreeID之外，每个节点还存储来自它的链路（属于Broadcast Tree的链路）的id。为了简单期间，这个链接被称为广播链路。

每个链路可以被从广播树中通过它的终端节点添加或删除。俩个终端节点都有关于链路是否为广播链路的最新信息。这可以通过确认消息等方式实现，它优先于广播相关的其他消息。

现在我们已经提出了算法建立和维护了广播树。它通过描述节点如何对不同的时间做出反应来完成，例如链接的建立或者停止，或者从邻居之一获得消息。

• 每当一个新的链接出现，以及俩个新的相邻节点认识到它们的TreeID不同时（即它们属于不同的广播树），那么这个个链路变为广播链路，并且俩个节点合并它们的广播树。合并树的TreeID是它们的TreeID中较大的一个。设G表示具有较大TreeID的节点，设S为另一个节点。因此，S更新它的TreeID到G的TreeID，并且之后启动新的TreeID描述的过程。
• 如果广播链接停止，即广播树分为俩部分，其中一部分会得到新的TreeID。首先停止链接的俩个端点将决定谁的树将获得新的TreeID。很明显这个决策必须在没有沟通的情况下做出。然而值得一提的是，如果它们都决定生成新的树，这不会导致问题，这个过程只会消耗更多的资源。例如一种简单的方式是，让具有较大NodeID的终端节点执行此进程。也就是这个节点生成一个新的TreeID（这个过程会在稍后描述），将其TreeID设置为值并启动NewID过程。终止链路的另一个端节点B等待获得新的TreeID一段时间。如果没有心的TreeID到达，这意味着节点A已完全断开和B的链接。然后节点B也以和A相同的方式产生一个心的TreeID，将其TreeID设置为值并启动一个NewID的过程。
• 新的TreeID的生成是相对简单的。如果之前的TreeID序列号为s，那么新的TreeID为(s+1,N)，其中N是执行此进程的节点的NodeID。如果新的节点产生，那么第一个TreeId为(0,N)其中N是NodeID。这个TreeID生成确保新生成的TreeID是唯一的，并且比前面一个节点的TreeID更大。
• 当一个节点在连接L上接收到“我有新的TreeID”消息，它将接收到的TreeID与自己的TreeID进行比较。如果收到小一点的，那么它必须废弃信息，什么都不做。如果它更大，那么节点集L为广播链路，更新它TreeID并且启动NewID程序。如果TreeID是相同的，那么意味着节点第二次获得这个TreeID，表示广播树和L将包含一个循环。为了解决这个问题，它让L设置为不是广播链接。

要求1，当网络进入稳态时，上述算法建立了一棵树，该树在(d+1)T时间内跨越链接其组件的所有节点，其中d为组件节点对之间最大的逐跳距离，T为发送“我有新ID”消息并接受节点处理所需的时间。

证明1. 在发送d个消息后，每个节点收到TreeID(s,N)的最大值。在发送一条消息之后，节点不生成与树维护相关的新消息，集合B的广播链路将会稳定。集合B就是TreeID(s,N)第一次被转发到某个及诶单的链路集合，因此B形成了一个联通的无环图。

3.2 广播机制

一旦广播树被建立，广播自身是非常简单的。广播消息由TreeID和消息本身组成。其中一个接地那接受广播消息，它将消息的treeId和自己的TreeID进行比较。如果不同，那么它删除消息因为它是过时的。如果它们是相同的，那么它在每一个消息广播链路上，除了它收到消息的那个上转发消息。只有广播消息的发起者才需要存储它。如果创建者需要更新其TreeId因为“我有新的TreeID”的消息在播出一定时间内发出。它得出的结论是，由于广播树的不一致，一些节点可能没有收到广播消息。然后节点根据消息的重要性决定是否重新广播该条消息。

如果本地广播是可用的，可以使用上述方法，不同之处是广播消息还包含节点N中获取该消息的节点的NodeID。接收到的广播只有在节点M不是在叶子节点的时候才会被转发。

附注

• 如果广播树在过渡状态，那么节点可能偶尔收到俩次或更多的广播消息。这种情况很少发生，而无论广播树是否进入稳定状态，消息都不会在广播树中循环，因此不会造成问题。
• 另一方面，如果广播树处于过渡状态，那么广播信息可能会不能达到每个节点。不幸的是这是一个不可避免的现象，如果出现链接终端，任何类型的广播机制都会出现这种情况。然而该算法确保广播树在网络变化后很快进入稳定状态，因此丢失信息的数量不回很大。此外，如我们在上面提到的，消息的发起者会在发起广播后的一定实现内获得新的TreeID，从而识别可能发生的这种现象。因此，这种情况下，它可以决重新发送这个消息。

4 性能和扩展性的提升

5 讨论

6测试行为和算法

7进一步的讨论和结论

这篇文章提出了TreeCast，一个新的广播方法适用于MANET。方法是基于完全的分布式的，去中心化的，维护生成树的高效算法。该算法还可以考虑节点的移动性，最大限度减少树的维护。为此我们提出了一个新的节点移动测量的方法，该方法仅基于节点连通性的变化，不需要任何GPS设备的地理数据。

算法在点对点传输下表现的特别好，因此，它对不支持点对多点传输的无线电技术网络特别有用。

这也确保了TreeCast不会受到IEEE 802.11b本地广播的负面影响。我们已经证明，对应屃办工类型的场景，我们的广播算法比文献中发现的广播算法表现的更好。 我们已经证明，ReeCast比传统的泛洪法更可靠。研究还表明，该方法能够高效、可靠地进行广播，使其对拓扑数据的处理比拓扑更适合实际的办公类型用户行为。

有几个方向可以继续。一个有趣的想法是使用TreeCast算法和它底层的生成树在网络中传播路由信息。那么上层的抽象便能够从隐式的骨干网络中获益。这是因为TreeCast强制高移动性的节点成为叶子。因此目前不移动的节点形成了一个相当可靠的骨干。若能见证某些路由算法（例如DST [14]）的路由信息通过TreeCast传播所带来的性能提升，那将是一件颇为引人入胜的事情。

另一个可能的方向是探索移动性措施的适用性，以增强现有MANET路由协议。例如包含稳定节点的线路可能比包含流动性节点的线路更受青睐。

引用

[1] A. Adams, J. Nicholas, and W. Siadak, "Protocol Independent Multicast—Dense Mode (PIM-DM): Protocol Specification (Revised)," IETF Internet-Draft, draft-ietf-pim-dm-new-v2-02.txt, Work in Progress, Oct. 2002.

[2] A. Ballardie, P. Francis, and J. Crowcroft, "Core Based Trees (CBT): An Architecture for Scalable Inter-Domain Multicast Routing," in Proc. ACM SIGCOMM, San Francisco, 1993, pp. 85–95.

[3] D. Estrin et al., "Protocol Independent Multicast—Sparse Mode (PIM-SM): Protocol Specification," RFC 2362, Jun. 1998.

[4] R. G. Gallager, P. A. Humblet, and P. M. Spira, "A Distributed Algorithm for Minimum Weight Spanning Trees," ACM Transactions on Programming Languages and Systems, vol. 5, no. 1, pp. 66–77, Jan. 1983.

[5] Z. J. Haas, M. R. Pearlman, and P. Samar, "The Bordercast Resolution Protocol (BRP) for Ad Hoc Networks," IETF Internet-Draft, draft-ietf-manet-zone-brp-01.txt, Work in Progress, Jun. 2001.

[6] IEEE, IEEE Specification 802.1D: MAC Bridges, D9, Jul. 14, 1989.

[7] C. Lee, M. H. Ammar, and J. E. Burns, "An Improved Leader Election Protocol in Multi-Hop Radio Networks," in Proc. International Conference on Computer Communication, Seoul, Korea, 1995.

[8] H. Lim and C. Kim, "Multicast Tree Construction and Flooding in Wireless Ad Hoc Networks," in Proc. 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2000, pp. 61–68.

[9] J. Moy, "Multicast Routing Extensions for OSPF," Communications of the ACM, vol. 37, no. 8, pp. 61–66, Aug. 1994.

[10] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," in Proc. ACM/IEEE MobiCom, Aug. 1999, pp. 151–162.

[11] N. Nikaein, H. Labiod, and C. Bonnet, "DDR: Distributed Dynamic Routing Algorithm for Mobile Ad Hoc Networks," in Proc. International Conference on Mobile Computing and Networking, 2000, pp. 19–27.

[12] C. E. Perkins, E. M. Belding-Royer, and S. R. Das, "IP Flooding in Ad Hoc Mobile Networks," IETF Internet-Draft, draft-ietf-manet-bcast-00.txt, Work in Progress, Nov. 14, 2001.

[13] C. Perkins, E. Royer, and S. Das, "Ad Hoc On-Demand Distance Vector (AODV) Routing," IETF Internet-Draft, draft-ietf-manet-aodv-11.txt, Work in Progress, Aug. 2002.

[14] S. Radhakrishnan, N. S. V. Rao, G. Racherla, C. N. Sekharan, and S. G. Batsell, "DST—A Routing Protocol for Ad Hoc Networks Using Distributed Spanning Trees," in Proc. IEEE Wireless Communications and Networking Conference, 1999, pp. 100–104.

[15] I. Stojmenovic, M. Seddigh, and J. Zunic, "Internal Node Based Broadcasting Algorithms in Wireless Networks," in Proc. Hawaii International Conference on System Sciences, Jan. 2001.

[16] J. Sucec and I. Marsic, "An Efficient Distributed Network-Wide Broadcast Algorithm for Mobile Ad Hoc Networks," CAIP Technical Report, TR-248, Jul. 2000.

[17] D. Waitzman, C. Partridge, and S. Deering, "Distance Vector Multicast Routing Protocol," RFC 1075, Nov. 1988.

[18] P.-J. Wan, K. M. Alzoubi, and O. Frieder, "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks," in Proc. IEEE INFOCOM, New York, Jun. 2002.