基于信号方差的Ad-Hoc网络路由算法

李 繁，张晓宇，刘 继

(1.新疆财经大学 网络与实验实践教学中心，新疆 乌鲁木齐 830012；2.新疆财经大学 统计与数据科学学院，新疆 乌鲁木齐 830012)

0 引 言

在Ad-Hoc无线网络中，移动主机任意移动的特性往往造成已选定的路径在封包传输的过程中，因中继点的移动使得传输发生中断，用户收不到数据的情况，从而增加了网络的不稳定性。即使所选择的路径能最快将封包送达用户，不稳定的路径仍会造成封包无法正确送达。另外，在移动主机的功率问题上，当中继节点数较少的路径被选择后，所有数据封包会以该条路径进行传输，由于该条路径使用率太过频繁，位于该路径上的所有节点将会消耗更多的电量，在有限的电池容量限制下也会因为电量不足造成路径中断，导致传输失败。

鉴于过去算法找寻最短路径却无法保证该路径是否稳定的缺点，本文提出一种有效的算法，利用信号强度的变动值作为路径选择的条件，具有以下特点：①信号强弱表示节点之间距离的远近，讯号越强表示两点的距离越靠近；信号越弱，表示两点的距离越来越远。②Ad-Hoc网络中的节点都是任意移动的，在一段时间内，观测每一个节点移动的变化，即可说明节点移动的程度。若某节点的信号变动值很小，表示其移动的范围不大，变化的程度平缓，则该节点的稳定度高。若某节点的信号变动值很大，表示其移动的范围很大，变化程度剧烈，则该节点的稳定性很低。③以信号变动值作为选择条件，可使路径具有不错的稳定度，提升封包传输的成功率。④所选的路径同时具有稳定性与较短路径的特性。

1 Ad-Hoc无线网络路径选择方法

在Ad-Hoc无线网络中，由于没有基站的支持，移动主机常常必须记录一些网络信息来维持路径的畅通，但不幸的是，这些信息却随着移动主机的移动而常常变动，而追踪这些变动点一般来说可分为两个方法，第一种称为表驱动(table-driven)方法，只要有一个移动主机变动位置(网络拓扑改变)，整个网络上所有的移动主机就必须更新他们的路径数据库[3，4]。这种方式不仅会使移动主机负担过重，还会造成网络带宽拥塞及需要大量存储器空间的缺点，但这种方法的好处就是每个移动主机所记录的数据都是正确而且是最新的，当需要路径时，可以直接从内存中寻找，立刻建立联机；另一种方法称为需求导向(on-demand)方法，顾名思义，就是需要路径的时候再开始去寻找，但由于路径找法是需要的时候才开始寻找，所以会有无法达到实时性的缺点，其优点就是不必一直更新内存内的路径表，并且不需用太多的内存空间来记录网络信息[5]，这两种方法各有优缺点，许多研究根据这两种方法提出不同的路由技术。本文以table-driven及on-demand为前提，将路由方法整理成三大类。

第一类是最短路径路由技术[6]。此类的路径选择是以该路径经过的中继点较少者为优先考虑，例如C.E. Perkins等提出的DSDV方法，是基于传统Bellman-Ford路由选择算法改良而发展出来的。一个以路由表(routing table)为基础的路由通信协议，意指每一个行动节点必须储存一个路由表，其中记录所有与该节点可能进行链接的节点及距离，路由表内的每笔记录同时也包含了一组序列号码(sequence number)，用来判断该笔数据的新旧情况，以避免各行动节点交换路径信息时发生拓扑结构改变，而产生“无穷计数”(count to infinity)的问题。另外，C.E. Perkins等又提出了AODV的方法。AODV 是以on-demand的路径建立方式，不同于DSDV通过网络拓扑状态改变来驱动路径信息的机制，只有在需要某端点路径信息的情况下，才对该端点进行路径寻找与建立的动作，不需固定周期性的去维护路径信息[7，8]。CGSR是建构在DSDV之上的路由协议。CGSR的机制是将整个网络划分成数个集群(cluster)，每个集群中选出集群管理者(cluster head)，由他们来负责管理集群内的成员和交换重要的相关信息，和记录整个网络的架构，这种方式是以table-driven为导向，非集群管理的节点就不必记录这些信息，如此一来，整个网络的每个节点所记录的总数据量就可以大大的减少。TORA将链接方向逆转(link reversal)的观念运用在Ad-Hoc无线网络上，是一种分布式的路由算法，非常适合在高度动态的环境下使用[9，10]。

第二类是利用全球卫星定位系统与Ad-Hoc无线网络路由协议结合应用。其相关研究有LAR、GRID等路由技术[11，12]。LAR(location-aided routing)利用GPS的位置信息来达到改善Ad-Hoc无线网络路由选择的效能。LAR的作法在于缩小寻找路径时的广播范围，同时又不影响其路径的找寻。首先假设每一个节点已知自己目前的位置，同时源节点知道目的节点在t0的位置L及目前的时间为t1并且假设源节点知道目的节点的平均速度V。有了这些信息，源节点可以由此推测出目的节点目前会在那个区域内，因此就可以得知预测区域(Expected Zone)。画出预测区域之后就可得知欲广播的范围，就是所谓的寻求区域(Request Zone)[13，14]。GRID协议通过卫星定位系统将网络分割成很多四方格且每个格子中选出一个靠近中心点的网关节点来记录格子内部的路由表，负责区域内部的通信，使用table-driven的方式。当网关节点要离开格子时就将路由表广播给格子内的其他成员，再由成员中选出代替的网关节点。区域之间的通信必须经由网关节点，使用on-demand的方式，除了源主机和目的主机之外，路径的中间点必为网关节点。

第三类是以路径稳定性(stability-based)为基础的路由技术，代表路由技术有ABR及SSA。ABR(associativity-based routing)的设计主要着眼于Ad-Hoc无线网络里节点间不稳定的链接关系，因此采用了关连(associativity)稳定性的概念，用来表示一个节点相对于相邻节点的链接的稳定程度。SSA(signal stability based adaptive routing)为on demand的路由技术，是以信号强度决定节点是否处于稳定状态，并且寻找一条能够维持一段时间而不断线的路径[15，16]。

2 以信号方差为基础的路由协议

本文提出了以信号方差为基础的路由选择算法SVR(signal variance based routing)。

2.1 协议概要

SVR是以信号方差为基础的路由算法，不同于过去Ad-Hoc无线网络路由算法中找寻最短路径的做法，SVR是以路径稳定性作为首要考虑的条件。在Ad-Hoc无线网络中，网络上的节点每隔一段时间会发出beacon与邻近节点通信。所谓beacon是指“我还活着”(I am alive)的信息，每隔一段时间，无线设备会交换此信息，用来维护彼此的联机状态。通过beacon得知节点之间的信号强度后，并纪录每一个节点的信号方差，再将此信号方差与节点的最大可通信范围(radio transmission range)做计算，得到一个链接稳定值(link stability value)之后记录在信号方差表(signal variance table，SVT)中。当来源节点需要路径时，会发出路径请求(route request)封包给邻近的节点，而邻近节点收到路径请求封包，若先前没有处理过该封包，则将记录在信号变动表中的链接稳定值存于封包中继续广播给邻近节点，直到送达目的节点为止。当目的节点收到来自不同地方传送过来的路径请求封包，计算每一条路径中所有链接的链接稳定值相乘的结果，值越大者，表示该路径的稳定性高，位于该路径上节点变动平缓；反之，值越小者，表示该路径的稳定度不高，位于该路径上的节点变动较大。因此，目的节点将以链接稳定值较大的作为路径的选择。目的节点选择了最稳定的路径后，沿着所选择的路径送出路径回复(route reply)封包，直到源节点为止。

2.2 协议细节

Ad-Hoc无线网络中，所有节点借着每隔一段时间发出的beacon与邻近节点通信，可得知节点间的信号强度。将收到的信号强度数据，利用式(1)及式(2)可得某邻近节点的信号平均强度值SSavg及信号方差值SSvar。t是指收到beacon的总次数，为时间单位；而S1…St是指纪录第一次beacon的信号强度值，到第t次的信号强度值

(1)

(2)

节点间的信号强度与距离的关系，以H.T. Friis提出的式(3)来看，Pr是指接收端的信号强度，Pt是指发送端的信号强度，Gt、Gr分别表示当发送端、接收端信号衰减时，用来增强信号强度的参数值，λ是指信号的波长，L指系统损失(system loss)，d是指发送端与接收端的距离。由公式可知信号强度与距离的平方有关系

(3)

信号方差是指节点间的位置移动情形，信号方差越大，表示每次beacon记录的信号强度不稳定，若节点A固定时间发出beacon给邻近节点B，侦测到的信号强度有强有弱，表示节点B忽而走远、忽而走近，因此节点B并不是一个稳定的节点，所计算出来的信号方差就会很大。若节点A侦测到节点C的信号强度值维持在一个平均值，表示节点C的位置变动平缓，计算出来的信号方差将会很小。由于每次 beacon都会产生一个新的信号强度值，若每得到一个新的信号强度值都要与旧的信号强度值重新计算，将会消耗许多计算机资源，例如内存空间、电池电量等，而且重新计算所花费的时间也会造成网络效能的延迟(delay)效应。因此，我们推导一个容易计算信号平均值与信号方差的公式(式(4)与式(5))，只要将新的信号强度值带入即可算出新的信号方差，如此可快速找寻一条稳定的路径，以利数据封包的快速传送，减少延迟的时间

(4)

(5)

假设收到新的信号强度值St+1，将此值带入式(4)、式(5)并与前次计算出来的信号方差SSvar及信号平均值SSavg做计算，即可得到新的信号方差NewSSvar及NewSSavg，最后再将新的SSvar及SSavg存放于SVT的SSvar与SSavg字段中。每个节点都维护着信号方差表，包含移动节点、Clicks、SSavg、SSvar、LSV等5个字段。

Clicks表示连续收到beacon的次数，每收到一次，则Click加1，若预期应收到beacon而未收到时，表示邻近节点已远离通信范围，此时则将Click设为0。LSV(link stability value)为一预估机率值，代表联机不中断的成功率，当LSV越高，表示两点间的链接(link)越稳定，越不容易断线；反之，若LSV越低，表示两点间的链接不稳定，随时都有可能断掉。本文提出两种LSV的计算方式：LSVSVR1及LSVSVR2。LSVSVR1是以信号平均强度为参数值所计算的机率值；而LSVSVR2是以信号变异值为计算LSV的参数值。以下将对于这两种方式做详细的说明。第一种方式是以信号平均强度为参数值，称为LSVSVR1。假设节点A最大可通信范围为Dradius，节点B的移动位置位于节点A的Dradius上，也就是说节点B的移动可能随时超出节点A的Dradius外，造成节点A无法与节点B通信的情形，如果在节点A所得到的节点B平均信号强度为SSavg，经由式(3)距离与信号强度的关系可推得节点A与节点B的平均距离为Davg1，Davg1等于Dradius时，节点A、B之间的LSVSVR1趋近于0；同样，另一节点C位于节点A的Dradius内，越靠近节点A，表示节点C移动的范围一直在节点A的附近，则节点A与节点C的LSVSVR1趋近于1，因此Davg2就越小，我们应让LSVSVR1越大。如图1所示。

图1 信号平均强度与链接稳定值的关系

以上是以距离的观点解释距离与稳定度的关系，而以信号强度的观点，SSavg若越大，代表距离越近(Davg越小)，因此LSVSVR1越大，假设SSmax代表每一节点可能收到的最大强度，我们推导出以信号强度平均值为基础的链接稳定度计算式(6)，由已知节点的平均信号强度值SSavg，即可算出LSVSVR1

(6)

除了平均信号强度值可用来解释节点信号与链接稳定值之间的关系外，另外，我们也利用信号强度变动值来说明节点的信号变动与链接稳定值之间的关系。第二种是以信号变异值为参数，称为LSVSVR2。假设某一节点移动较剧烈，对于另一节点的观测范围，此节点信号变动的范围最大将为SSmax，亦即此刻信号强度为SSmax，下一时刻信号强度可能立即为接近0的值，此种情形为信号最不稳定的情况。在一极端的情况下，所有的beacon中一半信号强度为SSmax，另一半的信号强度为0时，其信号强度的变动值SSvar不会超过SSmax/2上限值。由此可知，当信号方差SSvar等于SSmax/2时，我们将LSVSVR2值设为0，意指当节点变化越剧烈，它的信号方差很大，SSvar越大，则链接越不稳定，所计算出来的链接稳定值越小。反之，当信号方差SSvar等于0时，其LSVSVR2等于1，意指当节点变化越平缓，它的信号方差很小，SSvar越小，则链接越稳定，所计算出来的LSVSVR2越大。因此，我们可推导出式(7)，得知节点的信号方差SSvar，即可计算出LSVSVR2

(7)

2.3 路径搜索与回复程序

2.3.1 路径请求、回复封包格式

图2为路径请求封包格式，SEQ为一序列号码，一个节点可能同时收到不同来源的封包，序列号码用来判断封包是否先前处理过，一旦处理过该封包，则直接将封包丢弃(drop)，不再继续广播下去。TYPE为封包类型，包含UNICASTDATA、FLOODDATA、ROUTESEARCH、ROU-TEREPLY等类型。SRC及DEST分别为源节点的地址及目的节点的地址。TTL(time to live)指封包的存活时间，避免因封包产生错误而发生无穷循环(loop)的现象。HOP指经过的节点数。IN是指中间节点的地址，每经过一个节点，记录该节点的ID。METRIC存放LSV，当节点收到封包时，将记录在信号变动表中的链接稳定值储存在此字段，作为路径选择的判断条件。CRC(cyclic redundancy check)利用checksum来检查封包是否有错误。当某节点发出路径请求封包时，TYPE值为ROUTESEARCH代码，刚开始HOP为0，IN、METRIC字段不存在，路径请求封包每经过一个节点HOP值加1，IN、METRIC字段也会各多一笔。

图2 路径请求、回复封包格式

2.3.2 路径搜索程序

当节点S欲传送数据给节点D时，节点S会先将自己的地址及目的节点地址等信息存放于路径请求封包中，再将该封包广播给邻近节点A、B，节点A、B收到该封包后判断是否先前处理过封包，若无，则继续广播给邻近节点，若已处理过，则直接丢弃该封包，不再继续广播下去。当节点A收到封包时，将其ID及LSV分别储存在IN及METRIC字段，如此进行下去，每个节点都将自己的ID及LSV储存在路径请求封包中，当目的节点D收到来自不同地方的封包后，根据存放于封包中的ID及METRIC字段，得到多条路径数据，通过式(8)LSV的相乘得到一路径稳定值PSV(path stability value)，值越大者，表示路径越稳定。如图3所示。

图3 路径搜索程序

将LSV相乘的另一层意义在于：当越多的LSV相乘，由于每一LSV值小于1，所得到的PSV将越小，而越少的LSV相乘，所得的PSV越大。因此，我们最终选择一条PSV最大的路径，不但为最稳定的路径，同时也会是一条较短路径。因此，我们所提的路径选择方法，不仅确保路径的稳定度，也不会带来过大的通信延迟

PSV=LSV1×LSV2×…×LSVn

(8)

2.3.3 路径回复程序

决定最稳定的路径后，目的节点会往源节点方向送出路径回复封包(route reply packet)，当源节点收到该封包，表示节点S与节点D的路径已确定，立即开始做数据传送的动作。

2.4 范 例

图4为一ad hoc无线网络环境范例。网络上的每个节点都维护信号方差表，通过每段时间发出的beacon与邻近节点通信，可得知信号的变化，将得到的信号值计算出平均信号强度、信号方差及链接稳定值后，记录在信号方差表中，如节点A的信号方差表见表1。

表1 节点A的信号方差

图4 简单Ad-Hoc无线网络范例

当节点S需要一条到达节点D的路径时，节点S会发出路径请求封包给节点A、B，节点A收到封包，将LSV

及ID储存于路径请求封包的字段中，继续再将此封包广播下去，直到目的节点D收到此封包为止。节点D收到来自不同地方的路径请求封包，包含多条的路径数据，见表2。

表2 多条路径数据

当节点 D收到多条路径数据，将记录在封包里的LSV相乘，得到每条路径相乘后的PSV，值越大者表示该路径与其它路径比较起来较稳定，因此在这个例子当中，节点D会选择Path_4，而Path_4同时也是5条路径中的最短路径。决定路径后，节点D传送路径回复封包，直到来源节点S收到该封包，立即可做数据流的传送与接收。

3 实验分析

这里我们提出实验数据将SVR与最短路径算法及R.Dube等提出的同以信号稳定度为基础的SSA算法作比较。本文的比较对象-最短路径算法，泛指AODV、DSR等算法。我们针对路径的持续时间、找到路的机率与路径经过的hop数等进行一系列的比较。以下将说明我们在模拟之前所必须提出的假设和模拟的环境。最后，则是一些仿真结果的数据及分析。

3.1 模拟环境假设

在我们的研究中，仿真环境仅限于网络层(network layer)，对于数据链路层(data link layer)的细节，如MAC协议、多重存取所造成的干扰(multiple accessinterference)、功率下降、链接错误(link error)，并不加以考虑。而物理层以及信道(channel)的细节问题，也不加以考虑。也就是说，两个节点互相在传输范围内时，即可成功传送数据，反之，则接收不到数据。本文之所以不考虑上述状况，是因为以上问题可以用现有的IEEE 802.11等类似的通信协议加以解决，只要将本文建构在IEEE 802.11的协议之上，即可解决上述问题。

3.2 模拟环境参数设定

以下介绍模拟环境所设定的参数：

仿真区域大小：670m×670m

移动主机个数：50～200个

传输半径：150 m

模拟时间：100 s

移动速度：10～50 m/sec

移动模式：360度任意移动

Beacon 区间：2 s

节点移动比例：20～80%

3.3 仿真数据分析

3.3.1 稳定度分析

节点的个数、节点移动比例及节点移动速度都是影响路径稳定度的因素。我们利用SVR1、SVR2、ST这3种路由机制所找出来的路径，计算其在100 s的运行时间内，路径持续而不中断的时间，作为稳定度分析。SVR1、SVR2两种都为本文所提出的路由机制，其中SVR1是以信号平均强度作为计算LSV的参数值；而SVR2是以信号变异值作为计算LSV的参数值。ST是传统找寻最短路径(shortest path)的机制。我们针对节点移动速度的变化与路径持续时间进行模拟，将产生出来的数据制成见表3。

表3 节点移动速度与路径持续时间数据

在100 s的执行内，SVR1、SVR2路径持续时间长于ST时间及SVR1路径持续时间长于SVR2时间等会因为节点移动速度增加而使路径持续不中断的时间降低，原因在于当节点的移动速度加快，节点移动很容易超过可通信范围，导致路径的中断，因此节点移动速度越快，则路径持续时间越短。在节点移动速度为10的情形下，SVR1的路径持续时间高出传统ST的路径达近98%，而SVR2也高达近81%；而在节点移动速度为50的情形下，SVR1的路径持续时间高出传统ST的路径达近81%，而SVR2也高达近69%。由此可知，本文提出的两种机制，在路径稳定度方面与传统路由机制比较均有不错的表现。如图5所示。

图5 节点移动速度与路径持续时间关系

在节点的数目与路径稳定度的实验中，我们将节点数目与 SVR1、SVR2、ST这3种机制的路径持续时间制成见表4。

表4 节点数量与路径持续时间数据

节点数目越多，找到稳定的节点机率越高，因此以稳定度为优先考虑的SVR1及SVR2找到的路径持续时间会越长。当节点个数为50时，SVR1的路径持续时间高于ST达91%，SVR2的路径持续时间高于ST达86%；而在节点个数为200 时，SVR1的路径持续时间高于ST可达93%，SVR2的路径持续时间高于ST达88%。因此，节点数越多，SVR1、SVR2均有不错的表现。如图6所示。

稳定度分析的最后一个实验中，我们将670m×670m范围内的100个节点，假设其移动比例为20%～80%之间。移动比例为20%的条件下，表示100个节点中，有20个是属于较不会移动的节点，移动范围均在通信范围内，其它80个是属于较会移动的节点，移动范围可能随时超过通信范围。通过此参数的设定，观察不同的节点移动比例与稳定度的关系。在移动比例为20%的情形下，SVR1的路径持续时间高于ST达90%，SVR2的路径持续时间高于ST达84%；在移动比例为80%的情形下，SVR1的路径持续时间高于ST达96%，SVR2的路径持续时间高于ST达78%，SVR1及SVR2的路径持续时间高于ST的比例均维持在一个值，并没有太大的变化。原因在于，当变化不大的节点数越多，找到稳定的节点越容易，因此路径就越稳定。所以当节点移动比例值越高，表示较不会移动的节点数越多，ST的路径持续时间相对的提高。如图7所示。

图7 节点移动比例与路径持续时间关系

3.3.2 路由选择成功率分析

在此实验当中，执行100 s的时间内，我们针对4种路由机制可以成功找到路径的机率作比较。SVR1、SVR2、ST这3种机制在运行时间内，皆可以100%找到路径，而SSA利用信号强弱来找路径的机制最多只有将近20%找到路径，其余80%因为不符合SSA选择路径的条件而没有被选到。因此，当源节点需要路径时，采用SSA的机制将会很容易找不到一条适合的路径，导致无法做数据的传送与接收。图中可发现，当节点的移动速度越高，SSA找到路径的机率也随之增加。原因在于节点的移动速度越高，移动范围很容易进入另一节点的通信范围内，当另一节点正在找寻合适的节点时，该移动节点位置正好处于另一节点的旁边，对另一节点而言，该移动节点的信号强度非常强，以SSA的选择条件，则该移动节点会被选择到。但整体而言，SSA找到的路径的机率还是偏低。

3.3.3 路径长度分析

此实验在观察于不同的节点移动速度当中，SVR1与SVR2每次找到的路径长度与ST所找到的最短路径作比较。本文提出的方法偏重于“稳定度”的概念，也就是所找的路径将有稳定，不易断线的特性，而经过的hop数为次要考虑的条件。实验结果发现，SVR1与SVR2的路径长度只多于最短路径一个hop数。利用SVR1或SVR2与ST的路径长度比例得知，无论节点移动速度的快或慢，SVR1的路径长度皆多于ST的路径长度一个hop数；而SVR2的路径长度几乎与ST的路径长度一致。因此，本文提出的路由机制，不仅具有路径稳定的特性，路径长度也不会太长，一旦选择SVR1或SVR2作为路由机制，则在数据传输上将有不错的效能表现。

4 结束语

本文提出on-demand的路由选择算法，目的在于找一条最稳定且不易中断的路径作为数据的传输信道，颠覆传统以最短路径为主要考虑的观念。由实验结果发现，本文提出的两种机制在及路径成功率及路径稳定度上均有不错的表现，而在路径的长度方面，与传统最短路径的机制比较，相差无几。因此，本文提出的机制同时具有路径稳定及最短路径的特性，在数据传输的效能上，将是不错的路由选择机制。下一步，我们将进行路径维护机制的研究，对于路径中断、路径修复等问题提出行之有效的解决办法。