问题
- 广播的直接转发法是通过泛洪来进行的，一个移动节点第一次接收到一条广播消息后必须而且应该重播这条消息
- 网络中如果有n个移动节点，那么就需要将同一条广播消息广播n次
- 在CSMA/CA（Carrier Sense Multiple Access with Collision Avoid，即带有冲突避免的载波侦听多路访问）网络中，泛洪的缺点如下：
- 多余的重播，当一个移动节点决定将一条广播消息重播给自己相邻节点的时候，所有这些相邻节点却已经有了该条广播消息。
- 竞争，在一个移动节点广播一条消息后，如果其多个相邻节点决定重播该条消息，那么这些发送(全部离开附近的移动节点)可能产生严重的相互竞争。
- 碰撞，由于没有采用退避机制，缺乏RTS/CTS（Request To Send/Clear To Send请求发送/允许发送协议）控制分组交互，以及没有碰撞检测(CD)，所以很可能发生碰撞，导致更严重的损害。
概括起来，把跟泛洪有关的这些问题称为广播暴问题(Broadcast Storm Problem)
严重性
多余重播分析
白点为源节点，灰暗节点为中继转发节点
- 白色节点发出的消息只需要2次发送就能够将一条消息广播完毕
- 但是，如果不减少多余广播的话，所有节点均会广播，需要发送4次
- 白点为源节点，灰暗节点为中继转发节点
- 白色节点发出的消息只需要2次发送就能够将一条消息广播完毕
但是，如果采用洪范，所有节点均会广播，需要发送7次
分析产生原因
- 从不同天线发出的无线信号很可能相互重叠在一起
- 一副天线覆盖的范围为一个圆
- 图中灰暗程度表示信号重叠程度
- 图中所示很多区域被同一个广播分组覆盖多次
在最坏情况下，一个区域被同一个广播分组覆盖多达7次
分析重播代价
- 考虑如图情况
- 移动节点A发送一条广播消息，移动节点B决定重播这条消息
- 设
表示移动节点A的无线电波覆盖范围，
表示移动节点B的无线电波覆盖范围 - 移动节点B重播覆盖的其他区域（阴影部分）用
表示 - 设r表示移动节点A和B的无线电波覆盖范围的半径
- d表示移动节点A和B之间的距离
- 可以推导出
- 当d=r时，覆盖区域
最大
- 因此可见重播只能够提供0~61%的新覆盖范围(与前一次广播覆盖范围比较)
- 求平均值，假设移动节点B可以处于移动节点A的传输范围内任意位置
- 对上述求积分，积分区间为中心点在移动节点A的半径x的圆周[0，r]
- 得到平均值如下:
因此，经过前一次广播之后，一次重播平均只能够提供41%的新覆盖范围
现考虑现在考虑一条广播消息被接收到2次的情况
- 假定移动节点C决定在接收到移动节点A和移动节点B的广播之后进行重播
- 移动节点C重播的覆盖范围为
- 仿真在移动节点C传输覆盖范围内随机地产生移动节点A和移动节点B
- 发现平均
- 注意到在仿真中
- 不能从积分得到覆盖范围的计算值，而是通过离散估计得到覆盖范围的计算值
- 离散估计将覆盖区域划分成一个一个的细微栅格进行近似计算
这表明将一条消息重播到新的移动节点的概率是很小的
一个移动节点在接收到同一条消息k次后再重播该消息的效果
- 仿真在移动节点X的覆盖范围内随机地产生k个移动节点
- 计算出移动节点X覆盖范围与另外k个移动节点覆盖范围总和之差
- 用期望新覆盖范围EAC(k)表示这个值( Expected Additional Coverage, EAC)
- 图表示仿真结果(仍然是通过细微栅格估计得到的)
- 从图中可以看到
-
竞争分析
考虑这样的情况：移动节点A发送一条广播消息，同时有n个移动节点在接收这条消息。
- 如果所有这些移动节点都打算重播该条消息
- 由于在移动节点A周围的两个或者更多的移动节点很可能位置比较靠近而相互竞争无线媒介
因此可能发生竞争
分析n=2的较简单情况
- 设移动节点B和C是两个接收节点，移动节点B可以处于移动节点A的传输范围内的任意位置
- C为了完成与B的竞争，必须处在区域
内 - 所以，竞争概率等于
- 设A和B之间的距离为x
- 该概率积分，积分区间等于中心点在A的半径x的圆周[0,r]，得到竞争的期望概率为
- 随着n的增大，竞争概率越高
- 在移动节点A的传输范围内任意产生n个移动节点
- 开始仿真试验观测概率cf(n, k)，即这n个移动节点中有k个移动节点无竞争重播的概率(Contention-Free，CF)
- 仿真结果如图所示
- 从图中可以看到全部n个移动节点有竞争的概率在n≥6的时候迅速大于0.8
- 所以一个区域越拥挤(节点数越多)，该区域内的竞争严重
- 另一方面，有一个无竞争移动节点的概率[即，cf(n, 1)] 随着n的增大而急速下降。
- 而且，不大可能有更多的无竞争移动节点 [即，cf(n,k)， k≥2]
注意有k=n-1个无竞争移动节点意味着有n个这种无竞争移动节点，所以cf(n,n- 1)=0
碰撞分析
MANET网络没有基站和访问点( Access Point, AP)
- 这里主要研究在IEEE 802.11分布式协调功能(DCF)作用下的性能
- CSMA/CA机制要求移动节点在以下情况正确启动退避进程
- 刚好在该移动节点发送完一条消息之后
- 一个移动节点需要发送时，但是此时媒介却正处在忙状态，并且该节点正在执行前面已经启动的退避进程
- 在执行退避进程之前，必须首先从当前退避窗口中随机选择一个定时数值来设置退避定时计数器的值
- 如果该节点的干净信道评价(Clear Channel Assessment, CCA)机制检测到信道在过去的那个时隙(一段固定长度的时间)处于空闲状态，那么退避定时计数器减一
- 当退避定时计数器减到零的时候，则完成本次退避进程
- 考虑多个相邻节点接收同一个节点X的一条广播消息的情况
- 有几种原因将引起碰撞：
- 第一，如果节点X周围媒介空闲时间足够长，那么节点X的所有相邻节点均可能执行完其退避进程
- 因此节点X的所有相邻节点在接收到一条广播消息(并且经过了DIFS周期)后，就可能全部在同时刻开始重播
- 由于诸如RF时延和传输时延之类的原因而没有立即检测到载波，那么就极有可能出现碰撞
- 第二，由于在广播传输中没有预先采用RTS/CTS控制分组交互, 所以碰撞损伤更加严重
- 第三，一旦发生了碰撞，由于没有碰撞检测机制，即使一个正在被发送的分组的前面已发送部分已经被碰撞损坏，但是节点仍将继续发送该分组。分组越长，信道资源浪费越多。
- 在通常的IEEE 802.11 MAC操作规范中没有注意上述问题，或许是因为在这种场合下不需要考虑一点对多点通信
由于上述所有原因，所以MANET网络环境中的广播暴问题值得去深入和认真地研究
减轻方案
减轻广播暴问题的方法是禁止某些节点重播，以便降低重播的冗余度，从而减轻竞争和碰撞
- 这些策略的不同之处在于移动节点估计冗余的方法不同，如何收集信息以便帮助做出决策的方法不同
除了最后一种策略需要依靠一些本地连通性信息，其他所有策略都是全分布式操作
概率方案
减少重播的一种直观方法就是使用概率统计重播方法
- 一个移动节点第一次接收到一条广播消息后，以概率p重播该条广播消息
- 显然，当p=1时，概率统计重播法就等效于泛洪法
为了处理前面描述的竞争问题和碰撞问题，在重播该条广播消息之前应该等待一小段随机时延(若干个时隙)，这样各个重播的定时就能够互不相同
定时器方案
当一个移动节点在试图重播一条消息的时候，该条广播消息可能由于下述原因而受阻
- 媒介忙、退避进程运行，以及其他已排队等待发送的消息
- 因此，该移动节点在真正开始发送该条消息之前有机会多次接收到其他移动节点发送来的这条广播消息
- 一条消息被接收到k次后的期望新覆盖范围EAC(k)随着k的增大而迅速减小
- 当一个移动节点重播的期望新覆盖范围EAC(k)变得太小的时候，就可以防止该移动节点重播
- 这就是计数器方案的基础
- 特别是，使用一个计数器c来连续跟踪一条广播消息被接收到的次数，选择好计数门限值C
当c≥C时，禁止重播
该方案的详细描述如下:
- 第一步：当第一次接收到一条广播消息msg的时候，将计数器初始化为c=1。在第二步中如果再次接收到该条广播消息msg,那么中断等待进程而执行第四步
- 第二步：等待一段时间，该段时间等于随机的若千个时隙的长度。然后递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止
- 第三步：该条广播消息msg在空中传输，结束进程
- 第四步：计数器c加1。若c<C,则重新进入第二步被中断了的等待进程。否则，若c=C,则继续执行第五步。
第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程
注意：第四步中的“重新进入第二步被中断了的等待进程”的意思是：该移动节点应该返回到第二步，等待一段时间，其长度等于该移动节点应该继续完成从中断点开始之后剩余进程所需的剩余时间。
距离方案
在计数器方案中，使用计数器来决定一个重播是结束，还是继续进行
- 而在距离方案中，使用移动节点之间的相对距离来决定一个重播是结束，还是继续进行
- 例如，假定移动节点H第一次接收到移动节点S的一条广播消息
- 如果H和S之间的距离d非常短，那么H重播能够提供的新覆盖范围就非常少
- 如果d比较大，那么H重播能够提供的新覆盖范围就比较大
- 在极端情况下，即d=0，新覆盖范围也等于0
- 前面已经分析了距离d和新覆盖范围
之间的关系 因此，可以将距离d作为一种参数，移动节点H使用这个参数来决定是否需要重播
现在假定：在真正开始发送一条重播消息之前，该条消息已经被移动节点H接收到若干次
- 设H与发送该条消息的最近移动节点之间的距离为dmin
- H重播的新覆盖范围不会大于
- 可以使用dmin 作为评估是否需要重播的一个参数依据
- 假设dmin 的门限距离值为D
当dmin<D的时候，移动节点H停止重播发送
该方案详细描述如下:
- 第一步：当第一次接收到一条广播消息msg的时候, dmin初始设置为到达该条广播消息msg的广播移动节点的距离。若dmin<D, 则跳到第五步继续进行。在第二步中，如果又接收到该条广播消息msg，那么中断等待进程，跳到第四步继续进行
- 第二步：等待一段时间，该段时间等于随机的若干个时隙的长度。递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止
- 第三步：该条广播消息msg在空中传输，结束进程
- 第四步：如果离发送该条广播消息msg的移动节点的距离小于dmin，则更新dmin。如果新dmin<D，则进入第五步继续进行；否则，重新进入第二步被中断了的等待进程
第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程
下面说明如何获取距离信息
- 一种可能的方法是根据所收消息的信号强度来估计。特别地，设消息的发送功率为Pr、 接收功率为Pr
- n、c1、 C2分别表示与物理环境、载波波长、天线增益有关的常数
- 因为
和
可以测量得到，所以可以根据这个公式估计出距离d 因为知道距离和功率之间的关系，那么通过设置信号强度门限值，甚至可以用信号强度来直接代替距离
位置方案
如果能够获得广播移动节点的位置，那么就可以精确估算出新覆盖范围
- 这种方法可能需要定位装置(例如全球定位系统GPS接收机)的支持
- 为了不失一般性， 设一个移动节点的位置为(0, 0)
- 这里仅采用二维位置来阐述，事实上，诸如GPS接收机之类的装置能够提供经度、纬度、海拔高度的三维位置
- 假定一个移动节点从分别位于(xi,yi), (x2,x2), .. (xk,yh) 的k个移动节点接收到k条相同的广播消息
- 可以计算出该移动节点重播该条消息所能够提供的新覆盖范围
- 设AC [(x1,y1), (x2,y2), …(xk,yk)]表示被
除后得到的新覆盖范围 然后将其与预先定义的覆盖范围门限值A(0<A<0.61 )进行比较，据此决定该接收移动节点是否需要重播
该方案详细描述如下:
- 第一步：当第一次接收到一条广播消息msg的时候, AC初始设置为该移动节点重播所能够提供的新覆盖范围。若AC<,跳到第五步继续进行。在第二步中，如果又接收到该条广播消息msg，那么中断等待进程，跳到第四步继续进行
- 第二步：等待一段时间，该段时间等于随机的若干个时隙的长度。递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止
- 第三步：该条广播消息msg在空中传输，结束进程
- 第四步：更新AC。如果新AC<，则进入第五步继续进行;否则，重新进入第二步被中断了的等待进程
第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程
使用上述方案的一个困难是计算AC的代价，这跟计算若千个覆盖圆范围之间的很多交叉区域有关
- 当有4个覆盖圆范围的时候，这个问题就已经很困难了
- 一种可能的方法是使用栅格填充近似(Grid-Filling Approxomation)法进行估计
- 一种选择方法是使用凸多边形(Convex Polygon) 来决定是否应该进行重播
- 例如，如图
- 假设移动节点X从移动节点A、B、C接收到同一条广播消息
- 图(a)表明：如果移动节点X位于三个发送移动节点A. B、C构成的凸三角形内部，那么移动节点X重播的新覆盖范围非常小，甚至等于0
图(b)表明：如果移动节点X位于多边形外面，那么X重播很可能提供更大的新覆盖范围(阴影区域)。这些观察结果暗示：只有移动节点处在多边形外面的时候，该移动节点才会被允许重播
下面通过几何计算证明上述凸多边形近似法的正确性
- 如果多边形检验禁止移动节点X重播(X在多边形内部)，那么最坏情况下丢失的覆盖范围最多22%
- 经观察，当X处在多边形边上的时候，新覆盖范围最大
- 设A和B是该边界上的两个端点
- 图(c)所示，如果A和B离X的距离各自等于传输距离r，那么新覆盖范围最大
- 计算出图(c)所示的阴影部分的面积
- 所以当一个移动节点处在由先前发送节点位置形成的凸多边形范围内的时候
-
分群方案
上述方案是根据统计模型和几何学模型来估计一条广播消息的新覆盖范围
- 下面说明如何使用图形模型来开发一种方法
- 特地采用分群概念来推导广播暴解决方案
- 假定每个移动节点周期性地发送分组来通知其他移动节点自己的存在
- 因此任何移动节点都能够自行确定自己与其他移动节点的连通性
- 每个移动节点有一个唯一的身份识别码ID
- 按照如下方法构成各个群
- 具有本地最小ID的移动节点自行选为群首
- 群首移动节点与其相邻移动节点形成一个群，相邻移动节点叫着该群的成员
- 在一个群内，能够与其他群内移动节点通信的成员叫着网关
- 为了仔细考虑移动性问题，当两个群首碰到一起的时候，ID较大的那个首放弃其群首身份
- 如图所示一个分群的MANET网络例子
- 假定通过低层分群协议形成一个MANET网络的各个分群，并且得到有规律的维护
- 在一个分群内，群首在没有碰撞的条件下，其重播能够覆盖其群内所有其他移动节点
网关移动节点应该负责将广播消息传播到其他群内的移动节点，但是同时不需要非网关成员移动节点重播该消息
基于上述观察，广播暴问题的分群解决方案详细描述如下
- 第一步：当第一次接收到一条广播消息msg的时候，如果该接收移动节点不是网关成员移动节点，那么禁止重播，结束进程。否则，该接收移动节点或者是群首、或者是网关成员移动节点，跳到第二步继续进行
- 第二步：使用概率方案、计数器方案、距离方案、或者位置方案来决定是否需要重播
- 把前面介绍的方案合并起来就得到分群方案。第一步是防止非网关成员移动节点重播，然后第二步进一步利用其他信息(比如新覆盖范围)来减少重播。
方案评估
可达性( REachability, RE):
r是接收到某条广播消息的移动节点数量, t是实际发送该条广播消息的移动节点数量
若有收获，就点个赞吧
0 人点赞
