软件学报  2020, Vol. 31 Issue (6): 1802-1816   PDF    
节点度估计和静态博弈转发策略的Ad Hoc网络路由协议
王庆文1,2,3 , 戚茜4 , 程伟4 , 李冬4     
1. 西安建筑科技大学, 陕西 西安 710055;
2. 通信网信息传输与分发技术重点实验室, 河北 石家庄 050081;
3. 火箭军工程大学, 陕西 西安 710025;
4. 西北工业大学, 陕西 西安 710072
摘要: 针对Ad Hoc网络路由发现过程中广播路由请求分组导致的广播风暴问题,提出了一种基于节点度估计和静态博弈转发策略的Ad Hoc网络路由协议NGRP.NGRP考虑边界影响,采用分段函数的思想将网络场景分为中心、边和角区域,分别估算网络中节点在不同区域的节点度,避免了周期性广播Hello消息获取节点度导致的开销;NGRP路由请求分组的转发采用静态博弈转发策略,利用节点度估算参与转发路由请求分组的节点数量,将转发和不转发作为策略集合,设计效益函数,通过纳什均衡获得节点转发路由请求分组的转发概率,从而减少了路由请求分组广播过程中产生的大量的冗余、竞争和冲突,提高了路由发现过程中路由请求分组的广播效率.运用NS-2对协议的性能进行大量的仿真,结果表明:NGRP的分组投递率、路由开销、MAC层路由开销和吞吐率这4项指标明显优于AODV+FDG,AODV with Hello和AODV without Hello协议.
关键词: Ad Hoc网络    广播风暴问题    路由协议    节点度估计    静态博弈转发    
Node Degree Estimation and Static Game Forwarding Strategy Based Routing Protocol for Ad Hoc Networks
WANG Qing-Wen1,2,3 , QI Qian4 , CHENG Wei4 , LI Dong4     
1. Xi'an University of Architecture and Technology, Xi'an 710055, China;
2. State Key Laboratory of Science and Technology on Communication Networks, Shijiazhuang 050081, China;
3. Xi'an Research Institute of High Technology, Xi'an 710025, China;
4. Northwestern Polytechnical University, Xi'an 710072, China
Abstract: To alleviate the broadcast storm problem caused by broadcasting the route request packets in the route discovery process, a node degree estimation and static game forwarding based routing protocol (NGRP) for ad hoc networks is proposed. NGRP adopts the idea of piecewise function to estimate the node degree when the nodes are in center, borderline and corner area respectively, which avoids unnecessary overhead caused by broadcasting Hello message periodically. NGRP applies the static game forwarding strategy to forward the route request packets, where the number of participating wireless nodes is the node degree and the strategy set is forwarding and not forwarding. According to Nash equilibrium, the forwarding probability can be calculated. NGRPP reduces the redundant retransmission and the chance of the contention and collision among neighboring nodes in the networks, increases the efficiency of the route request packets forwarding. The simulation results demonstrate preliminarily that NGRP improves the packet delivery fraction and throughput, reduces the normalized routing load and normalized MAC load, which all compare with AODV+FDG, AODV with Hello and AODV without Hello.
Key words: ad hoc networks    broadcast storm problem    routing protocol    node degree    static game forwarding    

Ad Hoc网络是由一组带有无线收发装置的移动终端组成的一个临时性的多跳的自治系统, 具有组网快速灵活、不依赖基础设施等优点, 在民用和军用领域具有广泛的应用前景.路由协议是Ad Hoc网络核心支撑技术, 主要解决数据分组实时、可靠传输的问题.Ad Hoc网络节点高速移动导致网络拓扑的高动态变化, 加之无线链路的带宽、能量限制, 为实现高性能的路由协议带来了挑战.研究者提出的Ad Hoc网络路由协议可以分为主动路由协议、按需路由协议和混合路由协议这3种.3种路由协议中, 按需路由协议因为路由开销小、不需要维护全网络信息等优点, 倍受国内外研究者关注.

在按需路由协议中, 当源节点没有到目的节点的路由时, 需要采用广播路由请求的方式开启路由发现过程, 而路由发现过程的效率严重影响路由协议的整体性能.最简单的广播是洪泛, 其思想是:节点接收到非重复的广播分组, 随即重新广播分组.按需路由协议的路由发现过程中采用洪泛机制, 容易导致广播风暴问题:大量的冗余、竞争和冲突浪费了网络带宽, 消耗了节点的能量, 严重影响了Ad Hoc网络的性能.为了缓解广播风暴问题, 科研人员提出了多种广播方案, 这些广播方案可以分为确定广播方案和概率广播方案[1].确定广播方案在接收到广播分组的节点中选取一部分节点转发分组, 该方案的不足是:一部分节点可能会因为多次承担广播任务而耗尽能量, 导致网络连通性下降; 另一方面, 由于Ad Hoc网络拓扑的高动态变化, 给转发节点的选取带来了困难.概率广播方案中, 网络中的所有节点以概率的方式转发分组.相比确定广播方案, 概率广播方案在路由失败、网络攻击和动态拓扑条件下表现出更好的鲁棒性.概率广播方案中, 节点转发概率如何获取?是Ad Hoc广播协议亟需解决的关键问题之一.利用节点的节点度, 即节点的邻居数量来计算转发概率, 是一种有效的方式, 文献[2-6]进行了这方面的研究.然而, 上述研究需要节点需要周期性广播Hello消息获取节点度, 既消耗了节点的能量和信道的带宽, 又增加了网络开销.

为此, 本文提出一种基于节点度和静态转发博弈的Ad Hoc网络路由协议NGRP(node degree and static game forwarding based routing protocol for ad hoc networks).NGRP的贡献主要包括两个方面:一方面, NGRP考虑网络场景边界区域的影响, 将网络场景分为中间、边和角这3种区域, 采用分段函数的思想, 分别计算节点在网络场景的中间、边和角区域的节点度, 从而避免了节点周期性广播Hello消息导致的能量消耗和网络性能下降; 另一方面, NGRP在转发路由请求分组时采用静态博弈转发策略, 用节点度估算博弈转发的参加节点数量, 将转发分组与不转发分组作为策略集合, 设计效益函数, 通过纳什均衡获得转发概率, 提升了路由请求分组在路由发现过程中的广播效率.运用NS-2进行大规模的仿真, 仿真结果证明了NGRP在分组投递率、吞吐量、路由开销和MAC层路由开销等指标上的优越性.

本文第1节介绍相关工作.第2节论述考虑边界影响的节点度估计算法.NGRP协议及其实现过程将在第3节阐述.第4节运用NS-2对NGRP协议的性能进行仿真分析, 并与几种典型的路由协议的性能进行比较.最后, 对全文进行总结并对下一步的研究进行展望.

1 相关工作

在按需路由协议研究方面.经典的按需路由协议有AODV(ad hoc on-demand distance vector)[7], DSR (dynamic source routing)[8]等等.AODV协议的路由发现过程需要节点广播路由请求分组, 导致广播风暴问题, 严重降低了网络的整体性能.此外, AODV协议有两种运行模式, 周期性广播Hello消息和不广播Hello消息, 即便是广播Hello消息可以获得邻居节点的相关信息, AODV协议并没有充分利用.DSR协议与AODV协议的不同之处是在转发路由请求分组时, 节点将自己的信息添加到路由请求分组中, 这样路由请求分组中就包含了路径信息, 但是DSR协议并不能克服路由发现过程中的广播风暴问题.

在基于节点度的广播方案方面.文献[2]提出了一种基于博弈论的概率转发策略, 运用节点度信息获得转发概率, 并将其运用在AODV协议中, 实现了AODV+FDG协议, 仿真结果证明了该协议在路由开销、分组投递率和平均端对端延迟等性能优于AODV协议.文献[6]设定了转发概率的最大值和最小值, 并根据节点度调节转发概率, 使得转发概率在最大值和最小值范围内, 仿真结果证明了提出协议在转发节省率和冲突数量指标上显示出优势.文献[5]将节点度的倒数与常数因子的乘积作为转发概率, 提升了广播节省率, 该方案常数因子的选取还有优化空间.文献[3, 4]也做了类似的工作.文献[9]利用两跳节点度信息(即邻居节点的节点度)来计算转发概率, 当两跳节点度相对大时, 转发概率减少; 当两跳节点度相对小时, 转发概率增加.仿真结果表明, 该方案在分组投递率和路由开销两项指标显示了优越性.文献[2-6, 9]提出了基于节点度的广播方案, 并运用在具体的协议中, 虽然提升了网络协议的性能, 但是这些协议需要节点周期性广播Hello消息来获取节点度信息, 消耗节点能量和无线带宽的同时, 也增加了网络拥塞和路由开销, 影响了网络性能的进一步提升.文献[10]提出了一种基于邻居覆盖的概率广播协议, 通过设计新的广播延迟和广播概率方案, 提高了广播效率.文献[11]提出了一种基于估计距离的路由协议, 该协议在网络密度大或者是网络拓扑变化剧烈的情况下显著提高了路由性能.

为了克服广播Hello消息获得节点度的不足, 科研人员提出了不依赖Hello消息获得节点度的方法, 其中具有代表性的是文献[12-14].文献[12]利用节点在空间的分布函数, 计算出节点之间存在通信链路的概率, 然后利用概率和网络中节点的数量得出节点度信息, 不足之处是没有考虑到网络边界的影响.文献[13, 14]在计算节点度信息时考虑了网络边界的影响, 通过节点在网络区域的位置获得了节点度的期望值.该方法的不足在于:(1) 节点位置在任何区域时, 节点度都是相同的, 实际上节点位置在网络区域的边、角和中间区域节点度差异大; (2)该方法并没有获得解析解, 难以在协议中使用.此外, 文献[15, 16]研究了车载自组织网络的数据分发问题, 对本文的研究具有参考价值.

2 考虑边界影响的节点度的估计算法

本文采用分段函数的思想, 提出了考虑边界影响的节点度估计算法.假设节点的通信半径为R, n个节点分布在长宽分别为H, L的场景区域(其中, H > > R, L > > R), 节点的地理位置服从均匀分布.将场景分成为中间、边、角这3个区域, 分别用S1, S2S3表示, 如图 1所示.

Fig. 1 Geographic division of the erea 图 1 网络场景区域划分

以网络场景左下角为原点, 分别以场景左边界和下边界为y轴和x轴建立直角坐标系, 可得:

${S_1} = \left\{ {(x, y)\left| \begin{gathered} R < x < L - R \\ R < y < H - R \\ \end{gathered} \right.} \right\}$ (1)
${S_2} = \left\{ {(x, y)\left| \begin{gathered} \left( \begin{gathered} 0 \leqslant x \leqslant R \\ R \leqslant y \leqslant H - R \\ \end{gathered} \right){\rm{ or}} \\ \left( \begin{gathered} R \leqslant x \leqslant L - R \\ 0 \leqslant y \leqslant R \\ \end{gathered} \right){\rm{ or}} \\ \left( \begin{gathered} R \leqslant x \leqslant L - R \\ H - R \leqslant y \leqslant H \\ \end{gathered} \right){\rm{ or}} \\ \left( \begin{gathered} L - R \leqslant x \leqslant L \\ R \leqslant y \leqslant H - R \\ \end{gathered} \right) \\ \end{gathered} \right.} \right\}$ (2)
${S_3} = \left\{ {(x, y)\left| \begin{gathered} \left( {\begin{array}{*{20}{l}} {0 \leqslant x < R} \\ {0 \leqslant y < R} \end{array}} \right){\rm{ or}} \\ \left( {\begin{array}{*{20}{l}} {0 \leqslant x < R} \\ {H - R < y \leqslant H} \end{array}} \right){\rm{ or}} \\ \left( {\begin{array}{*{20}{l}} {L - R < x \leqslant L} \\ {0 \leqslant y < R} \end{array}} \right){\rm{ or}} \\ \left( {\begin{array}{*{20}{l}} {L - R < x \leqslant L} \\ {H - R < y \leqslant H} \end{array}} \right) \\ \end{gathered} \right.} \right\}$ (3)

其中, (x, y)代表节点的二维坐标.从图 1中可以看出:依据节点所处的地理位置, 考虑边界影响情况下的节点的通信范围可以分为3种情况来分析.

2.1 节点处于S1区域

当节点处于S1区域时, 节点拥有完整的通信范围, 如图 1中圆O1所示, 节点的通信范围为

${S_{{O_1}}} = \pi {R^2}$ (4)

此时, 节点的平均邻居个数可以估算为

${N_{{O_1}}} = \frac{{(n - 1)\pi {R^2}}}{{H \cdot L}}$ (5)
2.2 节点处于S2区域

当节点处在S2区域时, 由于网络场景有4个边界, 因而节点靠近边界区域可以分为4种情况.图 2中, 圆O2显示了节点靠近网络场景右边界的情况, 其中, BA, C的中点, O2B $ \bot $ AC.

Fig. 2 Node beside borderline 图 2 节点靠近边界区域

则, O2AO2B之间的夹角θ可以计算为

$\theta = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_2}B}}^2} }}{R}$ (6)

那么, 扇形区域O2CDA的面积可以计算为

${S_{{O_2}CDA}} = \frac{1}{2} \cdot 2\theta \cdot {R^2} = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_2}B}}^2} }}{R} \cdot {R^2}$ (7)

三角形O2CA的面积可以计算为

${S_{{O_2}CA}} = \frac{1}{2} \cdot {d_{{O_2}B}} \cdot {d_{AC}} = {d_{{O_2}B}} \cdot \sqrt {{R^2} - d_{{O_2}B}^2} $ (8)

那么, 节点O2在场景之外的面积可以计算为

${S_{ABCD}} = {S_{{O_2}CDA}} - {S_{{O_2}CA}} = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_2}B}}^2} }}{R} \cdot {R^2} - {d_{{O_2}B}} \cdot \sqrt {{R^2} - d_{{O_2}B}^2} $ (9)

因此, 可以得到节点O2的通信范围为

${S_{{O_2}}} = \pi {R^2} - {S_{ABCD}} = \left( {\pi - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_2}B}}^2} }}{R}} \right) \cdot {R^2} + {d_{{O_2}B}} \cdot \sqrt {{R^2} - d_{{O_2}B}^2} $ (10)

此时, 节点的平均邻居个数可以估算为

${N_{{O_2}}} = \frac{{(n - 1){S_{{O_2}}}}}{{H \cdot L}} = \frac{{(n - 1)\left[ {\left( {\pi - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_2}B}}^2} }}{R}} \right) \cdot {R^2} + {d_{{O_2}B}} \cdot \sqrt {{R^2} - d_{{O_2}B}^2} } \right]}}{{H \cdot L}}$ (11)

节点靠近上边界、下边界和左边界这3种情况的节点平均邻居个数, 同理可求.

2.3 节点处于S3区域

节点处于网络场景中角区域, 可以分为节点在网络场景的左上角、左下角、右上角和右下角这4种情况.

以节点处在网络场景的右上角为例, 该场景又可以分为两种情况.令${d_{{O_3}D}}$代表节点O3的圆心到右上角D的距离, 根据${d_{{O_3}D}}$与节点通信半径R的大小, 可以分为两种情况.

(1) 当${d_{{O_3}D}} \geqslant R$的情况.

当节点处于S3区域时, 节点的通信范围被两个边界所截, 如图 3所示.

Fig. 3 Node in a corner 图 3 节点靠近在角区域

根据公式(9), 此时, 节点O3的受边界影响无效的通信覆盖范围分别为

${S_{ABCK}} = {S_{{O_3}CBA}} - {S_{{O_3}CA}} = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}K}}^2} }}{R} \cdot {R^2} - {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{_{{O_3}K}}^2} $ (12)

同理:

${S_{EFGM}} = {S_{{O_3}GEF}} - {S_{{O_3}GE}} = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}M}}^2} }}{R} \cdot {R^2} - {d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{_{{O_3}M}}^2} $ (13)

此时, 节点O3的通信覆盖范围可以计算为

${S_{{O_3}}} = \pi {R^2} - {S_{ABCK}} - {S_{EFGM}}$ (14)
${S_{{O_3}}} = \left( {\pi - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}K}}^2} }}{R} - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}M}}^2} }}{R}} \right) \cdot {R^2} + {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{_{{O_3}K}}^2} + {d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{_{{O_3}M}}^2} $ (15)

此时的节点度可以计算为

${N_{{O_3}}} = \frac{{(n - 1)}}{{H \cdot L}} \cdot \left[ {\left( {\pi - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}K}}^2} }}{R} - \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}M}}^2} }}{R}} \right) \cdot {R^2} + {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{_{{O_3}K}}^2} + {d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{_{{O_3}M}}^2} } \right]$ (16)

(2) 当${d_{{O_3}D}} < R$的情况.

此时, 根据公式(9), 节点O3的受边界影响无效的通信覆盖范围SABCDK

${S_{ABCDK}} = {S_{{O_3}CBA}} - {S_{{O_3}CA}} = \arcsin \frac{{\sqrt {{R^2} - d_{_{{O_3}K}}^2} }}{R} \cdot {R^2} - {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{_{{O_3}K}}^2} $ (17)

节点O3的受边界影响无效的另一部分面积, 可以采用积分的方式求得:

设节点O3圆心坐标为$({x_{{O_3}}}, {y_{{O_3}}})$, 则圆O3的方程为

${(x - {x_{{O_3}}})^2} + {(y - {y_{{O_3}}})^2} = {R^2}$ (18)

可得:

$x = {x_{{O_3}}} \pm \sqrt {{R^2} - {{(y - {y_{{O_3}}})}^2}} $ (19)

对于图 4中的实例而言:

$x = {x_{{O_3}}} + \sqrt {{R^2} - {{(y - {y_{{O_3}}})}^2}} $ (20)
Fig. 4 Node in a corner 图 4 节点靠近在角区域

此时, 节点O3受边界影响无效的另一部分通信覆盖范围SDCGM

${S_{DCGM}} = \int_{{y_G}}^{{y_D}} {(x - L){\rm{d}}y} = \int_{{y_G}}^{{y_D}} {({x_{{O_3}}} + \sqrt {{R^2} - {{(y - {y_{{O_3}}})}^2}} - L){\rm{d}}y} $ (21)

因为:

${x_{{O_3}}} = L - {d_{_{{O_3}M}}}$ (22)

那么:

${S_{DCGM}} = \int_{{y_G}}^{{y_D}} {(\sqrt {{R^2} - {{(y - {y_{{O_3}}})}^2}} - {d_{_{{O_3}M}}}){\rm{d}}y} $ (23)
${S_{DCGM}} = \int_{{y_G} - {y_{{O_3}}}}^{{y_D} - {y_{{O_3}}}} {(\sqrt {{R^2} - {t^2}} ){\rm{d}}t} - \int_{{y_G}}^{{y_D}} {{d_{_{{O_3}M}}}{\rm{d}}y} $ (24)

进一步推导, 可得:

${S_{DCGM}} = \left( {\frac{t}{2}\sqrt {{R^2} - {t^2}} + \frac{{{R^2}}}{2} \cdot \arcsin \frac{t}{R}} \right)\left| {_{{y_G} - {y_{{O_3}}}}^{{y_D} - {y_{{O_3}}}}} \right. - {d_{{O_3}M}}({y_D} - {y_G})$ (25)

可得:

${S_{DCGM}} = \frac{{{d_{{O_3}K}}\sqrt {{R^2} - d_{{O_3}K}^2} - {d_{{O_3}M}}\sqrt {{R^2} - d_{{O_3}M}^2} }}{2} + \frac{{{R^2}\left( {\arcsin \frac{{{d_{{O_3}K}}}}{R} + \arcsin \frac{{\sqrt {{R^2} - d_{{O_3}M}^2} }}{R}} \right)}}{2} - {d_{{O_3}K}} \cdot {d_{{O_3}M}}$ (26)

结合公式(17)、公式(26)可得, 节点O3的受边界影响无效的通信覆盖范围SABCGMDK:

$\begin{gathered} {S_{ABCGMDK}} = \frac{{{R^2} \cdot \left( {2\arcsin \frac{{\sqrt {{R^2} - d_{{O_3}K}^2} }}{R} + \arcsin \frac{{{d_{{O_3}K}}}}{R} + \arcsin \frac{{\sqrt {{R^2} - d_{{O_3}M}^2} }}{R}} \right)}}{2} - \\ {\rm{ }}\frac{{{d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{{O_3}M}^2} + {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{{O_3}K}^2} }}{2} - {d_{{O_3}M}} \cdot {d_{{O_3}K}} \\ \end{gathered} $ (27)

那么, 节点O3的通信覆盖范围可以计算为

${S_{{O_3}}} = \pi {R^2} - {S_{ABCGMDK}}$ (28)

结合公式(27)、公式(28), 可得:

$\begin{gathered} {S_{{O_3}}} = \frac{{{R^2} \cdot \left( {2\pi - 2\arcsin \frac{{\sqrt {{R^2} - d_{{O_3}K}^2} }}{R} - \arcsin \frac{{{d_{{O_3}K}}}}{R} - \arcsin \frac{{\sqrt {{R^2} - d_{{O_3}M}^2} }}{R}} \right)}}{2} + \\ {\rm{ }}\frac{{{d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{{O_3}M}^2} + {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{{O_3}K}^2} }}{2} + {d_{{O_3}M}} \cdot {d_{{O_3}K}} \\ \end{gathered} $ (29)

此时, 节点的平均邻居个数可以估算为

${\tilde N_{{O_3}}} = \frac{{(n - 1)}}{{H \cdot L}} \cdot \left[ \begin{gathered} \frac{{{R^2} \cdot \left( {2\pi - 2\arcsin \frac{{\sqrt {{R^2} - d_{{O_3}K}^2} }}{R} - \arcsin \frac{{{d_{{O_3}K}}}}{R} - \arcsin \frac{{\sqrt {{R^2} - d_{{O_3}M}^2} }}{R}} \right)}}{2} + \\ \frac{{{d_{{O_3}M}} \cdot \sqrt {{R^2} - d_{{O_3}M}^2} + {d_{{O_3}K}} \cdot \sqrt {{R^2} - d_{{O_3}K}^2} }}{2} + {d_{{O_3}M}} \cdot {d_{{O_3}K}} \\ \end{gathered} \right]$ (30)

同理可估算节点处在网络场景左上角、左下角和右下角时的节点度.

3 基于节点度估计和静态博弈转发策略的Ad Hoc网络路由协议NGRP 3.1 节点度估计

NGRP假设网络中的节点携带定位装置, 知道自己的地理位置信息以及网络区域信息.网络中任意节点O首先利用自己的地理位置信息和网络区域信息, 依据公式(1)~公式(3)确定自己在网络场景中的位置区域; 然后根据节点在网络场景中所属区域情况, 分别计算节点度如下.

● 当节点处于网络场景的中心区域时, 依据公式(5)获得节点度;

● 当节点处于网络场景的边区域时, 运用公式(11)计算节点度;

● 当节点处于角区域且dODR时, 依据公式(16)获得节点度;

● 当节点处于角区域且dOD < R时, 运用公式(30)计算节点度.

综上, 结合公式(5)、公式(11)、公式(16)和公式(30), 在场景范围内的节点O的节点度可以估算为

${N_O} = \left\{ {\begin{array}{*{20}{l}} {{N_{{O_1}}}, {\rm{ }}O \in {S_1}} \\ {{N_{{O_2}}}, {\rm{ }}O \in {S_2}} \\ {{N_{{O_3}}}, {\rm{ }}O \in {S_3}~~{\rm{ and }}~~{d_{OD}} \geqslant R} \\ {{{\tilde N}_{{O_3}}}, {\rm{ }}O \in {S_3}~~{\rm{ and }}~~{d_{OD}} < R} \end{array}} \right.$ (31)

NGRP采用上一节提出的考虑边界影响的节点度估计算法获得节点度信息:一方面, 考虑网络场景边界区域的影响, 提高了算法获得节点度信息的准确性; 另一方面, 相比节点广播Hello消息获得节点度信息, 避免了不必要的开销.

3.2 静态博弈转发策略

NGRP本质上是一种按需路由协议, 当源节点有数据要发送而没有到目的节点的路由时, 发起路由发现过程.NGRP将路由发现过程中路由请求分组的转发过程看成一个静态博弈过程, 即参与转发路由请求的节点, 在做出决策时, 并不知道其他节点的策略, 参与博弈转发的节点之间没有关于博弈信息的交换.一旦节点做出决策后, 对博弈的发展不能再产生任何影响.静态转发博弈可以定义为

$ G=\left\{N_{O}, A, U\right\} $ (32)

其中,

NO代表参与转发路由请求分组的节点, 其数量可以由公式(31)计算得出;

A代表策略集合, 包含转发和不转发两个元素;

U代表效益函数, 见表 1.

Table 1 Forwarding dilemma game 表 1 转发困境博弈

表 1中, uv > 0.从表中可知:当NO个节点作为静态转发博弈的参与者, 选取其中任何一个节点作为当前节点进行分析.当前节点和其他NO-1都不转发分组时, 当前节点的收益为0;当前节点不转发分组, 由其他NO-1个节点中至少有一个节点转发分组, 当前节点的收益为u; 当前节点转发分组, 其他NO-1个节点不转发分组, 当期节点的收益为u-v; 当前节点和其他NO-1个节点都转发分组时, 当前节点的收益仍然为u-v.假设参与博弈的节点以固定概率P转发分组, 那么, 其他NO-1个节点至少有一个节点转发分组的概率为

${P_{{N_O} - 1}} = 1 - {(1 - P)^{_{{N_O} - 1}}}$ (33)

静态博弈分组转发的纳什均衡点为:当前节点转发分组时的收益与当前节点不转发分组, 其他NO-1个节点至少一个转发分组时的收益相等.即:

$u - v = u \times {P_{{N_O} - 1}}$ (34)

u=C×v, C为常数且C > 1, 带入公式(34), 可得:

$ G=\left\{N_{O}, A, U\right\} $ (35)

NO=1时, 令$P = 1$.

3.3 分组结构

NGRP的路由请求分组结构见表 2, 其中, 节点度信息被添加到路由请求分组中, 源节点地址和广播ID唯一标识一个路由请求分组.

Table 2 Routing request packet 表 2 路由请求分组

NGRP的路由表、路由回复分组和AODV的路由表和路由回复分组一样.

3.4 路由发现流程

NGRP协议的路由发现过程采用静态博弈转发策略, 转发概率由公式(35)得出, 具体步骤为:

● Step1:源节点有数据需要发送, 但是源节点没有到目的节点的路由, 此时开启路由发现过程.源节点获取自己的地理位置信息, 根据公式(31)估算自己的节点度NO, 并在路由请求分组中添加NO信息;

● Step2:中间节点接收到路由请求分组后, 判断是否重复接收:如果重复接收, 转Step7;否则, 转Step3;

● Step3:如果中间节点是目的节点, 发送路由回复分组; 如果中间节点不是目的节点, 但是中间节点有到目的节点的路由, 发送路由回复分组;

● Step4:中间节点不是目的节点, 且没有到目的节点的路由, 采用静态博弈转发策略, 根据公式(35)计算出转发概率P;

● Step5:产生[0, 1]之间的随机数m;

● Step6:如果m < P, 中间节点转发分组, 根据自己的地理位置信息依据公式(31)估算自己的节点度NO, 并将NO添加到路由请求分组中, 转发分组; 否则, 转Step7;

● Step7:丢弃分组.

NGRP的路由发现过程在AODV路由发现过程的基础上实现.NGRP的路由回复、路由修复过程继承了AODV的路由回复、路由修复过程.

4 仿真分析 4.1 仿真环境

仿真环境是带有CMU无线扩展的NS-2(Version 2.34), 仿真场景为2200m×600m的矩形区域, 此场景为常用场景, 节点的无线传输半径为250m, 网络带宽为2兆比特/秒, C取值为106.仿真分两组进行:(1)验证网络密度对协议性能的影响; (2)验证网络负载对协议性能的影响.仿真协议:(1) NGRP; (2) AODV+FDG; (3) AODV with Hello; (4) AODV without Hello.3个源节点的地理位置为(220, 60), (220, 300), (220, 540), 对应的目的节点地理位置分别为(1980, 540), (1980, 300), (1980, 60).仿真结果均为10次仿真的平均值.

表 3给出了两组仿真的公共参数.

Table 3 Simulation parameters 表 3 仿真参数

4.2 评价指标

本文用以下5个指标对协议性能进行评估.

(1) 平均端对端延迟Avdelay

$Avdelay = \frac{1}{N}\sum\limits_{i = 0}^N {({R_{time}}(i) - {S_{time}}(i))} $ (36)

其中, N表示成功传输的数据分组数, Rtime(i)表示第i个分组到达目的节点的时间, Stime(i)表示第i个分组的发送时间.

(2) 分组投递率Pdelivery

$Pdelivery = \frac{{{P_R}}}{{{P_S}}}$ (37)

其中, PR表示成功到达目的地的数据分组数, PS表示源节点发送的数据分组总数.

(3) 路由开销Nload

$Nload = \frac{{{P_C}}}{{{P_D}}}$ (38)

其中, PC表示节点网络层发送的控制分组的总数量, PD表示目的节点接收的数据分组总数.

(4) MAC层路由开销Mload

$Mload = \frac{{{P_M}}}{{{P_D}}}$ (39)

其中, PM表示节点MAC层发送的控制分组的总数量, PD表示目的节点接收的数据分组总数.

(5) 吞吐率Th

$Th = \frac{1}{{{T_{\operatorname{Re} nd}} - {T_{Rstart}}}}\sum\limits_{i = 0}^N {{R_{bytes}}(i) \times 8} $ (40)

其中, Rbytes(i)表示成功到达目的地的第i个分组的字节数, N表示目的地接收的总的分组数量, TRend表示网络中的数据分组结束接收的时间, TRstart表示网络中开始有数据分组接收的时间.

4.3 仿真结果

(1) 验证网络密度对协议性能的影响.

仿真方法:改变网络中节点的数量, 得到性能随网络密度变化的情况.移动节点数量分别为275, 300, …, 450, 源节点的分组发送速率为1个分组/秒.仿真结果如图 5~图 9所示.

Fig. 5 Average end to end delay 图 5 平均端对端延迟

Fig. 6 Packet delivery fraction 图 6 分组投递率

Fig. 7 Normalized routing load 图 7 路由开销

Fig. 8 Normalized MAC load 图 8 MAC层路由开销

Fig. 9 Throughput 图 9 吞吐率

图 5显示了平均端对端延迟性能随网络密度变化的情况.从图中可以看出:随着网络密度的增加, NGRP和AODV+FDG两种协议的延迟性能保持稳定, 而AODV with Hello和AODV without Hello两种协议的延迟性能出现波动.NGRP和AODV+FDG协议的平均端对端延迟性能明显优于AODV with Hello和AODV without Hello协议.原因在于:网络密度大时, NGRP和AODV+FDG采用概率的方式转发分组, 抑制了网络拥塞, 减少了节点间的竞争和冲突.

图 6显示了分组投递率性能随网络密度变化的情况.从图中可以看出:随着网络密度的逐渐增加, NGRP协议的性能保持稳定, AODV+FDG, AODV with Hello和AODV without Hello这3种协议的性能均出现了不同程度的抖动.NGRP的分组投递率明显优于其他3种协议, 原因在于:NGRP采用静态博弈转发策略, 采用考虑边界影响的节点度估计算法获得节点度信息, 避免了广播Hello消息带来的拥塞和开销.AODV+FDG和AODV with Hello两种协议的性能明显不如NGRP和AODV without Hello, 是因为前两种协议周期性广播Hello消息, 导致网络冲突增加, 进而导致分组投递率下降.

图 7显示了路由开销性能随网络密度变化的情况.从图中可以看出:网络密度的逐渐增加, NGRP和AODV without Hello的路由开销保持稳定, AODV+FDG和AODV with Hello的路由开销随网络密度的增加而增加.原因在于:AODV+FDG和AODV with Hello需要节点周期性地广播Hello消息, 增加了路由开销; 而NGRP采用静态博弈转发策略, 减少了网络密集情况下, 参与转发路由请求分组的节点的数量, 因而减少了路由层控制分组的数量.

图 8显示了MAC路由开销性能随网络密度变化的情况.从图中可以看出:NGRP和AODV without Hello的路由开销随着网络密度的增加基本保持稳定, AODV+FDG和AODV with Hello的MAC路由开销随网络密度的增加而增加.原因在于:AODV+FDG和AODV with Hello需要节点周期性地广播Hello消息, 导致MAC层控制分组数量; 而NGRP采用静态博弈转发策略, 减少了网络密集情况下参数转发路由请求节点的数量, 进而减少了MAC层控制分组的数量.

图 9显示了吞吐率性能随网络密度变化的情况.从图中可以看出:随着网络密度的不断增加, NGRP协议的性能保持稳定, 其他3种协议的性能均出现了不同程度的抖动, NGRP协议的性能明显优于其他3种协议.原因在于:NGRP采用博弈转发策略, 应用考虑边界影响的节点度估计算法, 不依靠Hello消息获得节点度, 拥有高性能的分组投递率和延迟性能, 因而吞吐率性能显示出优越性.

(2) 验证网络负载对协议性能的影响.

仿真方法:改变网络中源节点发送数据分组的发包率, 得到性能随网络负载变化的情况.移动节点数量为275个, 源节点每秒发送的数据包数量分别为1, 2, 4, 8, 16, 仿真结果如图 10~图 14所示.

Fig. 10 Average end to end delay 图 10 平均端对端延迟

Fig. 11 Packet delivery fraction 图 11 分组投递率

Fig. 12 Normalized routing load 图 12 路由开销

Fig. 13 Normalized MAC load 图 13 MAC层路由开销

Fig. 14 Throughput 图 14 吞吐率

图 10显示了平均端对端延迟性能随网络负载变化的情况.从图中可以看出:随着网络负载的增加, 4种协议的延迟逐渐变大.NGRP和AODV without Hello的延迟性能要优于AODV+FDG和AODV with Hello.原因是:网络负载的增加, 导致网络竞争、冲突加剧, 路由请求分组的重传次数逐渐增加, 源节点重启路由发现过程的数量增加, 因而延迟性能逐渐增加.NGRP采用概率转发策略, 不需要节点周期性发送Hello消息, 在一定程度上缓解了网络拥塞.

图 11显示了分组投递率性能随网络负载变化的情况.从图中可以看出, NGRP协议的分组投递率明显优于其他3种协议.当源节点的发包率小于每秒8个时, 4种协议的性能均呈现出先增加后减少的趋势, 原因在于:随着网络负载的增加, 到达目的节点的数据分组数量逐渐增加, 网络负载成倍增加, 而到达目的节点的分组数量没有网络负载增加快.当源节点的发包率大于每秒8个时, 4种协议的分组投递率剧烈下降, 原因在于:网络负载剧烈增加, 4种协议广播路由请求分组导致的剧烈的竞争和冲突.NGRP的转发策略和不广播Hello消息, 在此种情况下, 对网络性能起到了缓解作用.

图 12显示了路由开销性能随网络负载变化的情况.从图中可以看出:网络负载的逐渐增加, 4种协议的路由开销总体呈现先减少后增加的趋势.原因在于:随着网络负载增加, 到达目的节点的数据分组数量逐渐增加, 当网络负载增加到一定程度, 网络竞争冲突加剧, 分组投递率逐渐减少.NGRP和AODV without Hello的路由开销性能要明显优于AODV+FDG和AODV with Hello, 原因在于:NGRP协议缓解了路由发现过程中广播路由请求分组导致的广播风暴问题, 减少了网络中的冗余、竞争和冲突.

图 13显示了MAC层路由开销性能随网络负载变化的情况.从图中可以看出:网络负载的逐渐增加, 4种协议的MAC层路由开销总体呈现先减少后增加的趋势.原因在于:随着网络负载增加, 到达目的节点的数据分组数量逐渐增加, 当网络负载增加到一定程度, 网络竞争冲突加剧, 分组投递率逐渐减少.NGRP和AODV without Hello的路由开销性能要明显优于AODV+FDG和AODV with Hello, 原因在于:NGRP协议缓解了路由发现过程中广播路由请求分组导致的广播风暴问题, 减少了MAC层控制分组的数量.

图 14显示了吞吐率性能随网络负载变化的情况.可以看出, 4种协议的吞吐率均呈现出先增加后减少的趋势.当源节点的发包率小于每秒8个时, 随着网络负载的增加, 4种协议的吞吐率逐渐增加.当源节点的发包率大于每秒8个时, 网络拥塞程度加剧, 竞争冲突剧烈, 导致到达目的节点的数据分组数量有所降低.尽管如此, NGRP协议的吞吐率仍然优于其他3种协议, 原因在于:NGRP的路由发现过程缓解了广播路由请求带来的广播风暴问题, 减少了网络中的竞争和冲突.

5 结论及下一步工作

本文提出了一种基于节点度估计和静态博弈转发策略的Ad Hoc网络路由协议NGRP.NGRP采用考虑边界影响的节点度估计算法获得节点度信息, 避免了广播Hello消息导致的网络消耗; 采用静态博弈转发策略抑制路由发现过程中广播路由请求分组导致的广播风暴问题.运用NS-2, 从验证网络密度和网络负载对协议性能影响两个方面, 对NGRP协议性能进行验证.仿真结果表明:NGRP协议的分组投递率、路由开销、MAC层路由开销和吞吐率这4项指标均优于AODV+FDG, AODV with Hello和AODV with Hello协议.下一步的工作是将节点度估计算法和静态博弈转发策略引入到其他按需路由协议中.NGRP目前适用于网络节点数量较多且网络中节点分布均匀的场景, 还需要进一步改进协议, 才能适用于网络节点数量稀疏和节点分布不均匀的场景.

参考文献
[1]
Reina DG, Toral SL, Johnson P, Barrero F. A survey on probabilistic broadcast schemes for wireless ad hoc networks. Ad Hoc Networks, 2015, 25: 263-292. [doi:10.1016/j.adhoc.2014.10.001]
[2]
Mohammad N, Kemal T. Game theoretic approach in routing protocol for wireless ad hoc networks. Ad Hoc Networks, 2009, 7: 569-578. [doi:10.1016/j.adhoc.2008.07.003]
[3]
Lysiuk Ivan S, Haas Zygmunt J. Controlled gossiping in ad hoc networks. In: Proc. of the Wireless Communications and Networking Conf. (WCNC). IEEE, 2010.
[4]
Axel W, Horst H, Stefan F, Christiane S, Sándor F. AutoCast: An adaptive data dissemination protocol for traffic information systems. In: Proc. of the 66th Vehicular Technology Conf. (VTC 2007). IEEE, 2007.
[5]
Julien C, David S. Border node retransmission based probabilistic broadcast protocols in ad-hoc networks. In: Proc. of the 36th Annual Hawaii Int'l Conf. on System Sciences. IEEE, 2003.
[6]
Hanashi Abdalla M, Aamir S, Irfan A, Mike W. Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc networks. Simulation Modelling Practice and Theory, 2009, 17(2): 364-375. [doi:10.1016/j.simpat.2008.09.012]
[7]
Perkins CE, Royer EM. Ad-Hoc on-demand distance vector routing. In: Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99). 1999.
[8]
Johnson DB, Maltz DA, Hu YC, Jetcheva JG. The dynamic source routing protocol for mobile ad hoc networks (DSR): IETF Internet draft. 2002.
[9]
Reina D, Toral S, Jonhson P, Barrero F. Hybrid flooding scheme for mobile ad hoc networks. Communications Letters, IEEE, 2013, PP(99): 1-4. http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_2d12ba241c7af0ea5e11254896205969
[10]
Zhang XM, Wang EB, Xia JJ, Sung DK. A neighbor coverage-based probabilistic rebroadcast for reducing routing overhead in mobile ad hoc networks. IEEE Trans. on Mobile Computing, 2013, 12(3): 424-433. [doi:10.1109/TMC.2011.277]
[11]
Zhang XM, Wang EB, Xia JJ, Sung DK. An estimated distance-based routing protocol for mobile ad hoc networks. IEEE Trans. on Vehicular Technology, 2011, 60(7): 3473-3484. [doi:10.1109/TVT.2011.2158865]
[12]
Vieira Luiz Filipe M, Almiron Marcelo G, Loureiro Antonio AF. Link probability, node degree and coverage in three-dimensional networks. Ad Hoc Networks, 2016, 37: 153-159. [doi:10.1016/j.adhoc.2015.08.011]
[13]
Yoo Y, Agrawal DP. Optimal transmission power with delay constraints in 2D and 3D MANETs. Journal of Parallel and Distributed Computing, 2011, 71(11): 1484-1496. [doi:10.1016/j.jpdc.2011.05.004]
[14]
Yoo Y, Agrawal DP. Optimal transmission range with delay constraints for homogeneous MANETs. In: Proc. of the IEEE Int'l Symp. on World of Wireless, Mobile and Multimedia Networks (WoWMoM 2007). 2007.
[15]
Zhu JQ, Ma CM, Liu M, Chen GH, Gong HG, Liu B. Data delivery for vehicular ad hoc networks based on parking backbone. Ruan Jian Xue Bao/Journal of Software, 2016, 27(2): 432-450(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4839.htm [doi:10.13328/j.cnki.jos.004839]
[16]
Zhao H, Liu M, Liu NB, Gong HG, Zhou SE, Wu Y. Parked-Vehicle assisted data dissemination paradigm for urban vehicular ad hoc networks. Ruan Jian Xue Bao/Journal of Software, 2015, 26(6): 1499-1515(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4591.htm [doi:10.13328/j.cnki.jos.004591]
[15]
朱金奇, 马春梅, 刘明, 陈贵海, 龚海刚, 刘斌. 车载自组织网络中基于停车骨干网络的数据传输. 软件学报, 2016, 27(2): 432-450. http://www.jos.org.cn/1000-9825/4839.htm [doi:10.13328/j.cnki.jos.004839]
[16]
赵慧, 刘明, 刘念伯, 龚海刚, 周圣二, 吴跃. 城市车载网络中基于停放车辆辅助的数据分发. 软件学报, 2015, 26(6): 1499-1515. http://www.jos.org.cn/1000-9825/4591.htm [doi:10.13328/j.cnki.jos.004591]