Qos约束随机游走在移动自组网资源发现中的应用

董忠磊，范通让

（石家庄铁道大学 信息科学与技术学院，河北 石家庄 050043）

移动自组网是一种无基础设施的多跳无线网络，在移动自组网中每个节点同时充当着节点和路由的作用［1］，由于其组网灵活被广泛应用到抗震救灾、现场指挥、临时会议、资源共享等场合。移动自组网没有特定的网络中心，网络中的每个节点同时扮演着客户端和服务器的双重角色［2］，网络中节点的个体差异，使得不同的节点拥有的资源不尽相同，节点极为渴求自己所不具备的必要资源，但是却不能有一个“高层节点”统一满足，移动自组网中的服务发现协议应运而生。

随着多媒体应用日益普及，在移动自组网资源发现过程提供Qos已经逐渐成为移动自组网研究的一个重要领域，笔者研究提出了将Qos约束条件应用到移动自组网随机游走资源发现协议中，以此来提高移动自组网服务发现的质量。

1 相关工作

目前移动自组网中的关于资源发现问题得到了广泛的研究，已经提出了许多资源发现协议。文献［3］提供了一种针对节点运动速度较快的情况下的资源发现协议—泛洪查询。当某个主机需要某种资源的时候只需要发送一个针对该资源的查询广播就可以了。但是当网络中节点数量很大时，使用这种方式需要转发大量的资源发现包，严重增加了网络的负担。文献［4］提出了一种基于地理信息的资源定位协议（GCLP），这种方法因为需要获取地理位置信息并且周期性地广播地理信息所以同样耗费能量和带宽资源。文献［5］提出了应用于MANET的上下文相关的服务发现协议（CBSDP）。移动节点根据所处地理位置布置的传感器节点提供的环境信息，执行应用程序所规定的操作。文献［6］在理论上分析了分布式系统中使用Epidemic模型（模拟传染病的扩散过程）进行信息扩散的性能，给出了需要解决的问题以及影响性能的一些参数。文献［7］提出了一种基于场论的资源发现协议。每个节点都具有类似于电场中的电压，查询转发路径是随着资源“电压”高的节点进行。文献［9］提出了一种基于随机游走的资源发现协议。网络中的节点在查询转发时候使用随机游走方法，这种方法大大减少了网络中查询包的数量，降低了网络开销。但是以上几个提出的资源发现协议都没有考虑Qos，本文就是在文献［10］提出的随机游走资源发现协议的基础上加上Qos约束条件，来满足特殊应用对于Qos的需求。

2 Qos约束随机游走在移动自组网资源发现中的应用

2.1 移动自组网网络拓扑结构

考虑的移动自组网是由Laptop、PDA、智能手机等组成的网络，它们之间通过无线wifi、蓝牙或红外线等技术进行互连，具体的拓扑结构如图1所示。

2.2 Qos约束指标计算表达式

考虑的Qos约束指标主要包含节点剩余带宽（bandwidth）、延迟（link delay）、丢包率（packet loss rate），下面分别给出其计算表达式［8］。表1给出表达式当中所用到的符号、缩略词及其含义。

图1 移动自组网网络拓扑结构

表1 符号及其含义

（1）剩余带宽

节点的剩余带宽通过考虑节点无线信道状态即共享无线媒体的空闲时间来进行估算。每个节点在观察时间间隔TB内监听信道的状态来确定空闲时间。空闲时间Ii通过增加信道前一个忙碌时间结束到下一个忙碌时间开始的数目来计算。总的空闲时间包括几个空闲插槽n。总的空闲时间是所有n的总和。总的信道带宽BWtotal的计算公式如公式（1）所示。

（2）连接延迟

每个节点的连接延迟DL由输入队列延迟、处理延迟、传播延迟和重传延迟。Pi，a为包i到达节点的时间，Pi，c为确认数据包的时间。包的连接延迟为到达时间和确认时间的差值。在一定时间内m个数据包的平均延迟TD表达式为：

（3）丢包率

丢包是由于缓冲区溢出和重传引起的。丢包率PR为所有丢失包的总和，No为溢出所导致的丢包，Nr为重传包的数量，那么在一段时间TP内总的丢包率为：

通过以上得到的公式（1）、公式（2）和公式（3），在加入w1、w2、w3参数之后得到各个节点Qos计算表达式：

其中w1、w2、w3为根据用户对Qos需求各个指标所对应的权重，用户不同的Qos需求所对应w1、w2、w3的值也会不同，例如当用户对某项服务需求中的带宽占主要作用时w1的权重就会高于其它指标。

3.3 Qos约束随机游走资源发现协议

随机游走资源发现协议就是移动自组网节点在进行资源服务请求分发过程中采用随机游走方式，节点在接收到资源服务请求包后查看自身是否能够提供相应可利用资源，如果可以那么就给资源请求者发送回复包，反之把资源服务请求转发给随机挑选的邻居节点，这样一直循环执行下去直到找到满足服务要求的节点为止。

Qos约束随机游走资源发现协议将用户对节点在资源搜索过程中的Qos需求应用到随机游走协议中，使节点在转发资源服务请求时不只是随机的选取邻居节点作为下一跳，而且还要使用Qos来评估随机选取的节点是否能够达到要求，如果不能达到要求那么就舍弃，最终得到一条满足用户Qos需求的资源发现最优路径，具体步骤如下：

（1）移动自组网节点运行Qos约束随机游走资源发现协议，设定Qos阀值TS。

（2）资源请求节点发出资源服务请求包，节点利用随机游走协议随机的从其邻居节点中选取下一跳节点。

（3）资源请求节点搜集2步骤中挑选的下一跳节点信息（剩余带宽、连接延迟、丢包率、剩余电量）。

（4）资源请求节点利用第3步骤中搜集到的信息利用公式（5）进行计算求得下一跳节Qvalue点值，将Qvalue与Qos阀值TS进行比较如果大于或者等于那么保留节点，反之丢弃该下一跳节点。

（5）判断是否找到服务资源提供节点，如果找到则停止搜索过程，服务提供节点发送回复包，否则跳到步骤2，直到找到服务资源提供节点为止。

流程图如图2所示。

笔者提出的移动自组网Qos约束随机游走资源发现协议目前只是处于理论研究阶段，接下来将使用NS2网络仿真工具通过与未加Qos约束的随机游走资源发现协议进行仿真比较来验证改进协议的性能。

图2 Qos约束随机行走资源发现协议运行流程

4 结语

提出的Qos约束随机游走资源发现协议在原有随机游走资源发现协议的基础上加入Qos约束条件，使得节点在资源请求转发过程中更好的满足用户对Qos的需求，最终寻找一条满足资源请求者Qos需求的源节点到目的节点的最优路径。因此，对移动自组网相关领域还需要进行深入的研究，比如（1）考虑更多的Qos约束条件（节点剩余电量），（2）对Qos约束随机游走资源发现协议进行仿真实验，（3）通过实验来总结如何根据用户Qos需求合理的分配Qos约束条件的权重等等。

［1］Mahmoud Al－shugran，Osman Ghazali，Suhaidi Hassan，Kashif Nisarn，A.Suki M.Arif.A qualitative comparison evaluation of the greedy forwarding strategies in Mobile Ad Hoc Network［M］.Journal of Network and Computer Applications，2013（36）.887－897.

［2］R Iannella.Internet Resource Discovery Issues［EB/OL］.Available at archive.http：dstc.edu.au RDU reports Quest－Net95.html.

［3］Jivodar B.Tchakarov，Nitin H Vaidya.Efficient Content Location inWireless Ad Hoc Networks［C］.IEEE International Conference on Mobile DataManagement（MDM’04），IEEE Computer Society，Berkeley，California January，2004：74－87.

［4］Mohamed Khedr，Ahmed Kannouch.ACAN－AD HOC CONTEXT AWARE NETWORK［C］.Proceedings of the 2002 IEEE Canadian Conference on Electrical＆Computer Engineering.IEEE Computer Society，Manitoba，Canada，200：1342－1346.

［5］Patrick T Eugster，Rachid Guerraoui，Anne－Marie Kermarrec，etal.Epidemic Information Dissemination in Distributed Systems［J］.Computer，IEEE Computer Society，2004，37（5）：60－67.

［6］Vincent Lenders，Martin May，Bernhard Plattner.Service Discovery in Mobile Ad Hoc Networks：AField Theoretic Approach［C］.Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks（WoWMoM＇05）.IEEE Computer Society，Italy，2005：120－130.

［7］Hamideh Babaei，Mahmood Fathy，Morteza Romoozi.Modeling and optimizing Random Walk content discovery protocol over mobile ad－hoc networks［M］.Performance Evaluation，2014.18－29.

［8］V.R.Budyal，S.S.Manvi.ANFIS and agent based bandwidth and delay aware anycast routing in mobile ad hoc networks［M］.Journal of Network and Computer Applications，2014.140－151.