AD hoc网络的新按需路由协议

Marghny H.Mohamed¹马哈茂德。一个Mofaddel¹， Hamdy.H El-Sayed¹
埃及阿苏特大学计算机与信息学院计算机科学系。2埃及索哈格大学理学院数学系。

摘要

Ad-hoc网络是一个移动节点的集合，动态地形成一个临时网络，不使用任何现有的基础设施或集中管理。构建这样的网络面临许多技术挑战，如路由、能耗、负载平衡和安全性。移动自组织网络(manet)中的路由问题在满足一定的服务质量(QOS)要求时变得越来越复杂。本文研究了移动自组织网络在自组织网络特性下的路由问题。本文主要研究了网络拓扑结构变化、平均邻居节点数、节点数和传输范围等自组织网络特征的跳数和路径距离变化。比较了不同的拓扑结构，如圆形、正方形和矩形。我们的结果比较了这些特征对Ad-Hoc随需距离向量(AODV)和我们提出的算法Bee-Dijkstra算法(BDA)的影响。BDA和AODV中的路径路由和跳数都随着CTR (Critical Transmission Range)的变化而变化，说明CTR对网络连通性和路径路由有明显的影响。

介绍

Ad-hoc网络不依赖于任何预先建立的基础设施，因此可以部署在没有基础设施的地方。这在灾难恢复情况下以及需要快速部署通信的通信基础设施不存在或损坏的地方非常有用。在所有希望相互通信的用户之间形成ad-hoc网络意味着参与ad-hoc网络的所有用户必须愿意转发数据包，以确保数据包从源发送到目的。由于节点之间相互转发数据包，因此需要某种路由协议来进行路由决策。目前已有一些针对自组织网络路由协议的标准，其工作仍在进行中。在确定任何标准并在工业上应用之前，仍有许多问题有待解决。人工蜂群算法(Artificial Bee Colony, ABC)是近年来引入的一种基于蜂群的算法。ABC模拟了蜂群的智能觅食行为。Dervis Karaboga和Bahriye Akay[2]使用ABC算法对一组大型数值测试函数进行了优化，并将ABC算法的结果与遗传算法、粒子群优化算法、差分进化算法和进化策略的结果进行了比较。结果表明，该算法具有控制参数较少的优点，优于或近似于其他基于种群的算法。

在本文中，我们提出了一种新的优化算法。重点研究了响应式路由自组织网络算法的拓扑形状效应和传输范围效应。给出了平均邻居节点数、自组网面积、传输面积和节点密度等特性。研究了改变拓扑圆和正方形形状对两种算法的影响，即Ad-hoc按需距离向量算法(AODV)和Bee-Dijkstra算法(BDA)。我们的比较使用了新的特征，如跳数和路径开销参数，通过环形自组织网络。

CTR(临界传输距离)是产生连通通信图的最小传输距离，可以节省网络设备的能量。如果CTR小于最小值，则该图将断开。如果传输范围增大，路径可能与CTR状态下的路径不同，图会出现强连通。BDA和AODV中通过改变CTR改变路径路由，表明CTR对网络连通性和路径路由有明显的影响。

本文的其余部分组织如下。第2节介绍了群体智能。第三节提出了一种新的优化算法Bee-Dijkstra算法。第四节给出实验结果。第五节。得出结果。

群体智慧

近年来，群体智能已成为许多相关领域的研究科学家的兴趣。Bonabeau et al[3]将群体智能定义为“受群居昆虫群体和其他动物社会的集体行为启发而设计算法或分布式解决问题设备的任何尝试”。Bonabeau等[3]将观点集中在社会性昆虫上，如白蚁、蜜蜂、黄蜂以及其他不同种类的蚂蚁。然而，蜂群一词一般用于指相互作用的代理或个体的任何受限制的集合。蜂群的经典例子是蜜蜂在蜂房周围群集;然而，这个比喻可以很容易地扩展到具有类似架构的其他系统。同样，a flock of birds是指一群鸟。免疫系统[4]是一群细胞和分子就像人群[5]是一群人一样。粒子群优化(PSO)[6]是一种功能强大的算法，特别是在自组织网络中广泛应用的蜂群算法。

蜂群算法[7]是一种以蜜蜂觅食为灵感的群体智能优化算法。它是一种新的多变量、多模态连续函数优化器算法[8,9,10]。ABC算法将人工蜜蜂分为受雇蜂、围观蜂和侦察蜂三类。前半群由受雇的蜜蜂组成，后半群由围观的蜜蜂组成。对于每一个食物源，只有一只受雇的蜜蜂，被遗弃食物源的受雇蜜蜂成为侦察蜂。在ABC算法中，问题的每个解都被认为是食物源，用一个d维实值向量表示，而解的适合度对应于相关食物资源的甘露量。ABC算法也类似于其他基于群体智能的方法，即它也是一个迭代过程[11]。它从随机分布的溶液或食物来源开始。重复以下步骤，直到满足终止条件。

a.将被雇佣的蜜蜂送到食物源，计算花蜜的数量。

b.在分享受雇蜜蜂的信息后，由旁观者选择食物来源，并确定食物来源的花蜜量。

c.确定侦察蜂，并派它们去寻找新的食物来源。

ABC算法的伪代码

a.用随机解初始化population。

b .重复

C.把蜜蜂放在它们的食物来源上

D.根据蜜蜂的花蜜量把蜜蜂放在它们的食物来源上。

E.派侦察兵到搜索区域寻找新的食物来源。

f.记住目前找到的最好的食物来源

直到满足要求。

其次，将蜂群算法与dijkstra算法相结合，提出了一种发展蜂群算法的新思路。

提出的bee -dijkstra算法(bda)

本文提出的bee-dijkstra算法使用了在源路由中发挥突出作用的Dijkstra算法，其中搜索最优路由对manet[12]的路由性能起着重要作用。本文提出了一种新的优化算法，将食品锻造过程中蜜蜂的行为作为加工引擎使用的函数。该算法采用蜂群算法和Dijkstra算法相结合的方法。该算法首先将侦察蜂随机放置在搜索空间中。

Bee-Dijkstra算法为:

A.初始化人口

B.蜂巢里的蜜蜂

C.蜜蜂随机寻找食物

D.蜜蜂回到蜂巢

蜜蜂开始跳摇摆舞

f.确定蜂巢到食物的距离，使用dijkstra计算蜂巢到食物的最短距离(Short route)

G.蜂巢使用这条路径(路线)送蜜蜂去觅食，而不使用向导或地图。

h .结束

bee - dijkstra算法中的参数是食物源的数量等于受雇蜜蜂或围观蜜蜂的数量即Colony Size，工作蜜蜂率和终止程序[13]所需的循环次数或迭代次数(MCN)。

图1为bee dijkstra算法最短路径优化的实现流程图。在初始化阶段，对蜂群大小、迭代次数(MCN)和工蜂率等控制参数进行了设置。在下一阶段，流程图被作为输入与要访问的位置的数量。然后利用dijkstra算法得到路径。重置蜜蜂路径，侦察蜜蜂使用此路径，并更新工作蜜蜂的数量。当迭代次数完成并获得最佳路径和代价时，优化循环终止。

实验结果

我们的实验重点是Li Hui和Dan Yu模型[14]以及[15]和[16]中的扩展，研究了ad hoc网络的两个重要性质，邻居节点的平均值和节点数。覆盖形状为节点在其中移动的正圆。这个形状正好是可以从下面的方程计算的传输区域。

利用这个方程，我们可以计算出这个圆形状的半径R，如下所示

重点研究了响应式路由自组织网络算法的拓扑形状效应和传输范围效应。给出了自组织网络的传输范围、传输面积、传输面积和节点密度等特性。研究了改变拓扑圆形状对Ad-hoc按需距离向量算法(AODV)和Bee-Dijkstra算法(BDA)的影响。我们的比较采用了环形自组织网络的跳数和路径开销参数。

CTR(临界传输距离)是产生连通通信图的最小传输距离，可以节省网络设备的能量。如果CTR小于最小值，则该图将断开。如果传输范围增大，路径可能与CTR状态下的路径不同，图会出现强连通。

Ad hoc网络属性评估:

采用最小传输距离(CTR R=4.5)的二维10节点网络。网络将可能被连接。对AODV上的CTR和提出的网络路由算法BDA进行测试，测试结果如下:

在BDA状态:

在10个节点的网络中，CTR = 4.5时，从节点1到节点10的路径为1 - 2 - 6- 8 - 10，跳数为4，路径距离为14.5708。

在增加传输范围(R=6.5)后，路径变为1- 4 - 9 - 10，网络被认为是强连接的。跳数为3，路径距离为12.6056

AODV状态下:

在10节点的网络中，CTR = 4.5时。节点1到节点10的路径为1 - 2 - 3 - 4 -7 - 9 -10，网络已连通，跳数为6，路径距离为20.6588。当传输距离增大(R =6.5)时，网络中的路径变为1 - 2 - 3 - 4 - 9 - 8 -10，跳数为6，路径距离为25.6927。

BDA和AODV中的路径路由和跳数都随着CTR的改变而改变，说明CTR对网络连通性和路径路由有明显的影响。

圆的面积:

我们的实验结果考察了节点数、平均节点数、传输范围和网络面积等特征对圆拓扑形状的影响。然后，评估了这些特征在希望数和路径距离等参数上的变化。仿真在Matlab[17]中实现。测试了拓扑圆形状面积、平均邻居节点数和节点密度(节点数)的变化对跳数和路径距离的影响。

广场面积:

我们的实验结果考察了节点数、平均节点数、传输范围和网络面积等特征对方形拓扑形状的影响。然后，评估了这些特征在希望数和路径距离等参数上的变化。仿真在Matlab[17]中实现。测试了拓扑方形面积、平均邻居节点数和节点密度(节点数)的变化对跳数和路径距离的影响。

矩形面积:

我们的实验结果考察了节点数、平均节点数、传输范围和网络面积等特性对矩形拓扑形状的影响。然后，评估了这些特征在希望数和路径距离等参数上的变化。仿真在Matlab[17]中实现。测试了拓扑矩形形状面积、平均邻居节点数和节点密度(节点数)的变化对跳数和路径距离的影响。

结果讨论与分析:

本文研究了节点密度、平均邻居节点数、跳数和路径距离随传输面积和网络面积变化的拓扑变化等参数。对于表1、2、3、4、5、6、7、8和9所示的Ad hoc On Demand Distance Vector (AODV)和Bee-Dijkstra Algorithm (BDA)，计算最小跳数和最小路径代价。结果已显示在前面的表中。

首先在圆拓扑形状图(a)和(b) BDA比AODV更准确。从图中可以看出(a) BDA比AODV更有效率(b) BDA比AODV更稳定。图4显示:(a) BDA比AODV更准确(b) BDA比AODV更稳定。我们可以得出BDA在圆形时的性能优于AODV。

第二在方形图5 (a)和(b)中可以看出BDA比AODV具有最小的跳数和路径开销。图6 (a)和(b)分别说明了在跳数和路径代价上的平均邻居节点数，也说明了BDA比AODV具有最小的跳数和路径代价。图7描述了BDA比AODV更高效(a)和(b) BDA具有最小的跳数和路径成本。再次从前面的结果中我们可以得出结论，BDA在方形形状下比AODV具有更好的性能。

第三个矩形形状图8描述了BDA在(a)和(b)分别比AODV具有最小的跳数和路径代价。从图9可以看出，在(a)和(b)中BDA比AODV更准确。图10在(a)和(b)中节点数随跳数和路径代价的变化情况下，BDA比AODV更有效。从这些结果来看，BDA的性能优于AODV。

结论

随着manet的出现，由于manet本质上是高度动态和分布式的，因此需要新的路由方法。本文针对这些问题，提出了一种新的优化算法。讨论了无功路由自组织网络算法的拓扑形状效应和传输范围效应。给出了自组织网络的传输范围、传输面积、传输面积和节点密度等特性。研究了拓扑圆和正方形形状的变化对Adhoc按需距离向量算法(AODV)和Bee-Dijkstra算法(BDA)的影响。我们的比较使用了跳数和路径开销参数，通过圆形和方形的自组织网络。本研究的结论是BDA的性能优于AODV。未来的工作是在这些算法中加入信号强度等因素，使路由算法能够适应动态拓扑结构。

参考文献

Ahmed M. Abd Elmoniem, Hosny M. Ibrahim, Marghny H. Mohamed, Abdel-Rahman Hedar:“基于蚁群算法的移动自组织网络路由优化”，M.Sc提交给计算机与信息学院，计算机科学系，阿西特大学，埃及(2012)。
Dervis Karaboga, Bahriye Akay:“人工蜂群算法的比较研究”，应用数学与计算214(2009)108-132。
E. Bonabeau, M. Dorigo, G. Theraulaz:《群体智能:从自然系统到人工系统》，纽约:牛津大学出版社，1999年。
L.N. De Castro和F.J. Von Zuben:“人工免疫系统。第一部分:基础理论与应用”，技术报告第Rt Dca 01/99, Feec/Unicamp，巴西，1999。
J. Vesterstrøm和J. Riget:“数值优化中改进局部、多模态和动态搜索的粒子群扩展”，MSc。论文，2002年5月。
J. Kennedy和R. C. Eberhart:“粒子群优化”，《1995年IEEE神经网络国际会议论文集》，第4卷，1942-1948页，1995年。
Ajith Abraham, Ravi Kumar Jatoth, A. Rajasekhar:“混合差分人工蜂群算法”，计算与理论纳米科学杂志，第9卷，1 - 9,2012。
D. Karaboga:“基于蜂群的数值优化思想”，技术报告，TR-06，厄西耶斯大学工程学院，计算机工程系(2005)。
D. Karaboga和B. Basturk:“一种强大而高效的数值函数优化算法:人工蜂群(ABC)算法”，全球优化杂志，施普林格荷兰，第39卷，第459-471页，(2007a)。
D. Karaboga和B. Basturk，求解约束优化问题的人工蜂群(ABC)优化算法，LNCS:软计算的进展:模糊逻辑和软计算的基础，斯普格- verlag, IFSA, pp. 789-798，(2007b)。
Ajith Abraham, Ravi Kumar Jatoth, A. Rajasekhar:“混合差分人工蜂群算法”，计算与理论纳米科学杂志，第9卷，1 - 9,2012。
P.B.Pankajavalli和n.a arumugam:“DADSR:一种基于蚁群优化的manet动态源路由算法”，《欧洲科学研究杂志》，ISSN 1450-216X Vol.53 No.4, 2011。
Ashita S.Bhagade和第五段。Puranik:“基于人工蜂群算法的车辆路径优化问题”，国际软计算与工程学报(IJSCE)，第2卷，第2期，2012年5月。
H.Li D。于:“ad hoc网络中邻居节点属性的统计研究”，计算机工程学报，2002年第1期。
B.Ishibashi, R.Botaba:“移动自组织网络的拓扑和移动性考虑”，自组织网络处理3，第762-776页，2005。
AAA.Radwan, E.A. Zanaty和H.H El-Sayed:“Ad Hoc网络中邻居节点对拓扑和移动性的影响研究”。统计计算机科学与运筹学年会，开罗，埃及，2007年12月。
MATLAB (7.11.0 (R2010b))， Mathworks, http://www.mathworks.com