在实时manet环境中，减少路由开销的概率重播

C.Rajan^＊1, C.Dharanya², Dr.N.Shanthi^3.

印度蒂鲁钦戈德兰加美理工学院信息技术系助理教授。
印度蒂鲁钦戈德兰加美理工学院信息技术系p.g.学者。
印度南达工程学院计算机科学与工程系院长。

摘要

移动自组织网络(manet)由一组可自由移动的移动节点组成。这些节点可以动态地自组织成任意拓扑网络，而不需要固定的基础设施。manet是一个高度动态的网络，因为节点可以随时加入和离开网络。它的网络容量有限。在这样的网络中，服务质量通常受到由于能量消耗或移动节点的迁移而导致的网络破坏的限制。节点的移动会导致频繁的链路断裂，从而导致频繁的路径故障和路由发现。路由发现的开销不可忽视。本文讨论了一种减少实时MANET环境下路由开销的概率重播方法。

关键字

移动自组织网络，动态网络，路由开销，邻居覆盖和网络连通性

介绍

移动自组织网络(MANET)是一种由无线链路连接的移动路由器(和相关主机)组成的自配置网络，无线链路的联合形成随机拓扑。路由器可以自由地随机移动和组织自己;因此，网络的无线拓扑结构可能会迅速而不可预测地变化。这样的网络可以以独立的方式运行，也可以连接到更大的Internet。最小配置和快速部署使自组织网络适用于紧急情况，如自然或人为灾害、军事冲突、紧急医疗情况等。

传统的manet路由协议负责节点间路由的建立和维护。现有的路由协议可以分为主动路由协议和被动路由协议。例如，目的有序距离向量(DSDV)，优化链路状态路由(OLSR)，响应式/按需，如Ad hoc按需距离向量路由协议(AODV)[12]，动态源路由协议(DSR)，时间有序路由算法(TORA)和混合，如混合Ad hoc路由协议(HARP)，区域路由协议(ZRP)试图只提供最佳努力交付。它们的目标仅限于找到最小跳数或最短路径[16]。

在manet中，不断变化的网络拓扑结构会导致链路断裂和端到端的路由终止。路由协议需要解决链路故障预测问题。在传统的按需路由协议中，使用泛洪来发现到特定目的地的路由。它们向近邻广播一个RREQ包，这种广播引起了RREQ包过多的冗余重传，导致广播风暴问题[2]，从而导致大量的包碰撞，特别是在密集网络中。因此，对该广播机制进行优化至关重要。

广播协议分为四类。它们是“基于概率的方法、简单泛洪法、邻居知识法和基于面积的方法”。以上四类广播协议，它们表明静态网络中节点数量的增加会降低基于概率的方法和基于区域的方法的性能。

Kim et al.[4]表明邻域知识方法的性能优于基于区域的方法，基于区域的方法的性能优于基于概率的方法。

为了设计一种简单、可扩展、健壮和节能的多播路由协议，这些问题都被考虑在内。MAODV (Ad hoc on- demand Distance Vector routing protocol)是建立和维护一个共享的组播路由树，将数据从一个源发送到一个组播组的接收者。

文献综述

为了便于网络内的通信，使用路由协议来发现节点之间的路由。这种自组织网络路由协议的主要目标是在一对节点之间建立正确和有效的路由，以便能够及时地传递消息。路由构建应以最小的开销和带宽消耗完成。Ad-hoc路由协议是一种约定或标准，它控制节点如何同意在MANET中计算设备之间路由数据包的方式。在自组织网络中，节点对其周围网络的拓扑结构没有先验知识，它们必须发现它。其基本思想是，一个新的节点宣布其存在，并侦听来自其邻居的广播公告。节点了解新的临近节点和到达它们的方法，并宣布它也可以到达这些节点。随着时间的推移，每个节点都知道所有其他节点以及如何到达它们的一种或多种方式。最近，随需应变路由协议中减少路由发现和维护相关的路由开销的问题引起了越来越多的关注。

Huang[9]提出了一种根据网络情况动态调整Hello定时器和Timeout定时器的方法。例如，在高移动性网络中，需要使用较小的计时器值来快速检测网络中的变化。另一方面，在低移动性网络中，拓扑结构保持稳定且变化较少，设置较大的定时器值可以更有效地减少路由开销。为了判断网络的移动性是高还是低，我们使用了一种简单的方法来实时估计链路变化率。通过稍微增加数据流量的丢弃率，极大地降低了开销。丢包增加1%左右，开销减少40%。

Aminu[10]提出了一个重播概率函数，该函数考虑了报文计数器的值以及一些关键的仿真参数(即重播概率函数)。，网络拓扑大小，传输范围和节点数量)，以确定给定节点的适当重播概率。根据这些参数计算节点的重播概率。仿真结果表明，与其他方案相比，counter Function在不牺牲到达能力的情况下，在中等和密集网络中获得了更好的保存重播和端到端延迟。

Ould-Khaoua[11]提出了两种新的概率路由发现方法。分别是AP (Adjusted probistic route discovery)和EAP (enhanced Adjusted probistic route discovery)。这解决了现有按需路由协议中的广播风暴问题。转发概率是通过考虑发送节点的局部密度来确定的。在密集网络中，为了在不降低网络吞吐量的前提下降低路由开销，将位于稀疏区域的节点的转发概率设置为较高，而位于密集区域的节点的转发概率设置为较低。EAP-AODV降低了71%的开销，而APAODV降低了55%的开销。

MAODV[8]是AODV协议的组播扩展。基于共享树的MAODV按需连接多播组成员。MAODV具有单播、广播和组播功能。MAODV协议可以在搜索多播时获得路由信息;它还可以增加单播路由知识，反之亦然。当一个节点希望加入一个多播组，或者它有数据要发送到组中，但没有到该组的路由时，它会发出一个路由请求(RREQ)消息。只有组播组的成员响应加入RREQ。如果一个中间节点接收到一个多播组的加入RREQ，而它不是其中的成员，或者它接收到一个路由RREQ，而它没有到那个组的路由，它将把这个RREQ重新广播给它的邻居。但如果RREQ不是一个连接请求，则多播组中的任何节点都可以响应。

为了减少路由开销，提高路由性能，采用了组播技术。

基于邻居覆盖的概率转播(ncpr)协议

本文提出了基于邻居覆盖的概率转播协议[12]，该协议将邻居覆盖和概率方法相结合。为了有效地利用邻居覆盖知识，我们需要一个新的重播延迟来确定重播顺序，然后我们可以获得更准确的附加覆盖率。为了保持网络连通性并减少冗余重传，我们需要一个名为连通性因子的度量来确定有多少邻居应该接收RREQ包[13]。在此基础上，结合附加覆盖率和连通性因子，引入重播概率，减少RREQ报文的重播次数，提高路由性能。

A.转播延迟:

提出了一种计算重播延迟的方案。重播延迟是用来决定转发顺序的。与前一个节点有更多共同邻居的节点时延越低。如果这个节点重播一个数据包，那么更多的普通邻居将知道这个事实[14]。因此，这种重播延迟使得发送过报文的节点的信息能够传递给更多的邻居，这是该方案成功的关键。当一个节点ni从它之前的节点收到一个RREQ报文时，节点可以使用RREQ报文中的邻居列表来估计它的邻居有多少没有被RREQ报文覆盖。如果节点ni有更多的邻居被来自s的RREQ报文发现，这意味着如果节点ni重广播RREQ报文，RREQ报文可以到达更多的邻居节点。为了充分利用邻居覆盖知识，应尽快传播邻居覆盖知识。当节点s发送RREQ报文时，其所有邻居ni, i = 1,2…接收并处理该RREQ报文。假设节点nk与节点s有最多的共同邻居，节点nk的延迟最小。 Once node nk rebroadcasts the RREQ packet, there are more nodes to receive the RREQ, because node nk has the largest number of common neighbors. Node nk rebroadcasts the RREQ packet depends on its rebroadcast probability calculated in the next subsection. The objective of this rebroadcast delay is not to rebroadcast the RREQ packet to more nodes, but to disseminate the neighbour coverage knowledge more quickly. After determining the rebroadcast delay, the node can set its own timer.

B.重播概率:我们还提出了一种计算重播概率的新方案。该方案考虑了未覆盖邻居的信息、连通性度量和局部节点密度来计算重播概率。重播概率由两部分组成:a)附加覆盖率，即单次广播应覆盖的节点数与邻居总数的比率;b)连通性系数，反映给定节点的网络连通性与邻居数的关系。重播延迟较大的节点可能会侦听来自降低一个[13]的节点的RREQ报文。我们不需要调整重播延迟，因为重播延迟是用来确定传播邻居覆盖知识的顺序的。当节点ni的重播延迟定时器过期时，节点获取最终的未覆盖邻居集。属于最终未覆盖邻居集的节点是需要接收和处理RREQ包的节点。注意，如果一个节点没有从它的邻居中检测到任何重复的RREQ包，它的未覆盖邻居集不会被改变，这是初始的未覆盖邻居集。现在我们研究如何使用最后的未发现邻居集来设置重播概率。度量Ra表示该重广播额外覆盖的节点数量与节点ni的邻居总数的比率。 The nodes that are additionally covered need to receive and process the RREQ packet. As Ra becomes bigger, more nodes will be covered by this rebroadcast, and more nodes need to receive and process the RREQ packet, and, thus, the rebroadcast probability should be set to be higher. Xue [3] derived that if each node connects to more than 5.1774 log n of its nearest neighbours, then the probability of the network being connected is approaching 1 as n increases, where n is the number of nodes in the network. Then we can use 5.1774 log n as the connectivity metric of the network. We assume the ratio of the number of nodes that need to receive the RREQ packet to the total number of neighbors of node ni is Fc(ni).If the local node density is low, the parameter Fc increases the rebroadcast probability, and then increases the reliability of the NCPR in the sparse area. If the local node density is high, the parameter Fc could further decrease the rebroadcast probability, and then further increases the efficiency of NCPR in the dense area. Thus, the parameter Fc adds density adaptation to the rebroadcast probability. In this section, we calculate the rebroadcast delay and rebroadcast probability of the proposed protocol. We use the upstream coverage ratio of an RREQ packet received from the previous node to calculate the rebroadcast delay, and use the additional coverage ratio of the RREQ packet and the connectivity factor to calculate the rebroadcast probability in our protocol, which requires that each node needs its 1-hop neighbourhood information.

C.算法说明:

算法[1]给出了减少路由发现开销的基于邻居覆盖的概率重广播(NCPR)的形式化描述。

26:结束if

NCPR协议需要通过Hello报文获取邻居信息，也需要在RREQ报文中携带邻居列表。因此，在我们的实现中，采用了一些技术来减少RREQ报文中Hello报文和邻居列表的开销，具体如下:

•为了减少Hello报文的开销，我们没有使用周期性Hello机制。由于节点发送任何广播报文都可以通知邻居节点自身的存在，因此RREQ、RERR (route error)等广播报文可以起到Hello报文的作用。为了减少Hello报文的开销，我们采用了如下的[15]机制:只有当最后一个广播报文(RREQ、RERR或其他广播报文)的时间间隔大于HelloInterval时，节点才需要发送Hello报文。HelloInterval的值等于原AODV的值。

•为了减少RREQ报文中邻居表的开销，每个节点都需要监控其邻居表的变化，并在收到的RREQ报文中维护邻居表的缓存。我们修改AODV的RREQ报头，增加一个固定字段num neighbors，表示RREQ报文中邻居列表的大小，num neighbors后面是动态邻居列表。在RREQ报文发送或转发的两个相邻时间间隔内，任意节点ni的邻居表存在以下3种情况:

1)如果节点ni的邻居表至少增加了一个新邻居nj，则节点ni将num个邻居设置为正整数，即列出的邻居数，然后在RREQ报文的num个邻居字段后填充它的完整邻居列表。这是因为节点nj可能没有缓存节点ni的邻居信息，因此节点nj需要节点ni的完整邻居列表;

2)如果节点ni的邻居表删除了一些邻居，则节点ni将num邻居设置为一个负整数，与删除邻居的数量相反，然后只需要在RREQ报文的num neighbors字段后填充已删除的邻居;

3)如果节点ni的邻居表不变，则节点ni不需要列出邻居，将num个邻居设置为0。

从节点ni收到RREQ报文的节点，可以根据收到的RREQ报文中num个邻居的值进行操作:

1)如果num neighbors为正整数，则节点根据收到的RREQ报文中的邻居列表替换节点ni的邻居缓存;

2)如果num neighbors为负整数，则更新节点ni的邻居缓存，并删除收到的RREQ报文中删除的邻居;

3)如果num neighbors为0，则节点不执行任何操作。由于2和3两种情况，该技术可以减少RREQ报文中邻居列表的开销。

结论

本文讨论了一种基于邻居覆盖的概率重播协议，以减少manet的路由开销。该邻居覆盖知识包括附加覆盖率和连通性因子。提出了一种动态计算重播延迟的新方案，用于确定转发顺序，更有效地利用邻居覆盖知识。由于减少了冗余重播，该协议减轻了网络冲突和争用，从而提高了数据包的传递比，降低了平均端到端延迟。最后，采用组播的方式减少路由开销，保持网络的服务质量。

参考文献

张新明，王恩博，夏晶晶，宋丹根，高级成员，IEEE,2012。一种基于邻居覆盖的概率重广播在移动Ad hoc网络中降低路由开销。
倪淑莹、曾玉春、陈玉生及薛俊平。“移动自组织网络中的广播风暴问题”，ACM/IEEE MobiCom ' 99，第151- 162,1999。
B. Williams和T. Camp，“移动Ad Hoc网络的广播技术比较”，ACM MobiHoc ' 02，第194-205页，2002。
J. Kim, Q, Zhang和D. P. Agrawal，“移动Ad hoc网络中基于覆盖区域和邻居确认的概率广播”，IEEE GLOBECOM ' 04, 2004。
张晓明，王恩波，夏俊杰，宋德凯，“一种基于估计距离的移动自组织网络路由协议”，电子工程学报，vol.60,no. 1。7, pp.3473 - 3484年9月。2011.
J. D. Abdulai, M. Ould-Khaoua, L. M. Mackenzie和A. Mohammed，“邻居覆盖:移动自组织网络的动态概率路由发现”，SPECTS ' 08 Proc.， pp. 165-172, 2008。
J. Chen, Y. Z. Lee, H. Zhou, M. Gerla，和Y. Shu，“有损耗无线环境的健壮Ad Hoc路由”，MILCOM ' 06版，pp. 1- 7,2006。
Elizabeth M. Royer和Charles E. Perkins:“Ad hoc按需距离矢量路由协议的组播操作”，第五届ACM/IEEE移动计算与网络国际会议(MobiCom)论文集。8月207至218号(1999年)。
D. Johnson, Y. Hu和D. Maltz，“IPv4移动自组织网络(DSR)的动态源路由协议”，RFC 4728,2007。
Mohammed, M. Ould-Khaoua, L.M. Mackenzie, C. Perkins和J. D. Abdulai，“移动自组织网络的基于概率counter的路由发现”，WCMC ' 09版，第1335-1339页，2009。
X. Wu, H. R. Sadjadpour，和J. J. Garcia-Luna-Aceves，“路由开销作为节点移动性的函数:主动路由的建模框架和含义”，IEEE MASS ' 07, pp. 1- 9,2007。
r.莫汉，c .拉詹，n。Shanthi，“MANET路由协议的稳定移动模型评估策略”，IJARCSSE, 2012年12月。
J. D. Abdulai, M. Ould-Khaoua和L. M. Mackenzie，“改进移动自组织网络中的概率路由发现”，IEEE本地计算机网络会议论文，第739-746页，2007。
网络模拟器- ns-2 http://www.isi.edu/nsnam/ns/。
张晓明，王益斌，夏俊杰，宋德凯，“基于估计距离的移动自组织网络路由协议”，IEEE, 2013。车辆技术，第60卷，no. 1。7，第3473-3484页，2011年9月。
P. Chandra Sekhar, M.R. Pavan Kumar, K.S. Ranjith, E. Purushottam, Ch. Koteswararao，“实时MANET环境中路由开销的影响”IJCTA，第4卷(2)，257-263,2013年4月。
Vinayak T. Patil，助理教授，S。Dandannavar，“一种用于降低移动Ad Hoc网络路由开销的新转播技术”，IOSR-JCE, 2013年8月。