路由特性对IEEE 802.11 DCF多跳网络容量的影响
时间：2010-03-25 12:14:53
手机看文章
扫描二维码
随时随地手机看文章
[导读]使用数学分析方法研究基于IEEE802．11 DCF的Ad Hoc网络中节点传输半径和路由策略选择问题。在节点均匀分布的多跳网络中，使用四种路由策略以及不同的节点传输半径设置，试图找出能够使网络容量最大化的方案组合。计算结果表明，在节点密度一定的情况下，减小网络节点的传输距离有利于增加网络的容量，而在传输半径一定的条件下，使用能够导致长跳路由的策略，有利于提高网络容量。
0 引言
对于Ad Hoc或传感器网络这样的多跳无线网络来说，信源节点与信宿节点通常不在对方的传输覆盖范围内，因此在传送信息时需要经过中间节点的转发。在转发过程中，对路由的选择可以有两种策略：短跳路由策略，即数据转发过程使用由多个短距离链路组成的路由；长跳路由策略，即数据转发过程使用由少量的长距离链路组成的路由。
不同路由策略对网络传输容量带来的影响是一个值得关注的问题。对此，一些研究给出了不同的观点。文献[1]认为在一个干扰受限的网络中，每跳的距离越短，网络的传输容量越高。文献[2-4]则从分析网络干扰的角度，研究了长跳／短跳路由问题，认为网络中可能存在一个最佳的传输半径设置，能够使网络的容量达到最大。尽管这些文献的观点并不相同，但是它们之间并不存在直接的对立，原因是它们所假设的网络条件不同(其中，最主要的是网络中MAC协议的差别)。笔者认为，对于网络性能所进行的分析应根据实际的网络条件来进行，不存在普遍适用的准则。
在多跳网络中，路由协议和MAC协议的互动会对网络性能产生很大的影响，因此将这两个层次的技术结合起来进行性能分析是必要的。近年来，IEEE 802.11已经成为无线局域网中一个主要的国际标准，其中基本的接入机制是分布式协调功能(DCF)。随着Ad Hoc网络技术在军事、商业等领域的应用，IEEE 802.11DCF作为主流接入协议之一受到了更多关注，因此本文研究的多跳网络则基于这种MAC协议。使用数学分析方法，研究了在IEEE 802.11 DCF多跳网络中，路由策略和节点传输半径设置对网络容量的影响问题。
1 路由特性对多跳网络容量的影响
在多跳网络中主要有两种不同的因素会对最终生成的路由长跳／短跳特性产生影响：
(1)节点功率(传输半径)设置的影响
如果节点功率设置较低，传输距离较短，必然会造成传输路由为短跳路由。这会对网络容量带来双重影响，有利的方面包括：小的传输距离意味着信道的空间复用能力提高，网络中可以有更多的传输同时发生；节点传输范围内的平均邻节点减少，由于分组碰撞而导致传输失败的概率减小。不利的方面则是：分组需要更多的跳数才能到达最终的目的节点，传输过程中出现失败而丢弃分组的概率增加；为完成同样数量的端到端业务传输，网络节点的平均转发次数增加，致使网络内部更加繁忙。这在一定程度上抵消了由于空间复用能力增加而带来的好处。如果节点功率设置较高则情况相反。
(2)路由策略的影响
在网络节点功率设置确定的情况下，不同的路由策略也会造成最终生成的路由特性不同。倘若发送节点使用的路由协议(或策略)倾向于选择距离自己近的邻节点作为下一跳的转发节点，则最终生成的路由必然是短跳路由。反之，则会导致长跳路由。
路由协议对网络性能的影响可参照图1来说明：在多跳网络中，基于载波监听的MAC协议(如：IEEE 802.11 DCF)都需要面对隐藏终端问题。当节点S发起传输后，处于节点D独占区(用B(S，D)表示)的节点无法监听到节点S的信号，因此可能在此次传输进行期间发起新的干扰传输，造成S，D之间传输失败。显然，B(S，D)区域的面积越大，隐藏终端的数量越多，传输失败概率也就越大。然而，B(S，D)区域的面积大小则受到路由策略的影响。
基于以上原因，在多跳网络中，对于MAC层性能的研究应结合特定的路由策略以及功率控制方案来进行才更有意义。此外，虽然路由策略和节点功率设置都可能造成路由的短跳／长跳特性变化，但是这两种因素对网络性能的影响机制是有差别的。例如：当节点的发送功率确定时，改变路由策略可以造成路由长跳、短跳的特性不同，但通常对网络中信道的空间复用能力没有影响。在进行研究时，应该对这两种因素的影响进行区分。
本文所进行的研究，基于如下的网络条件假设：
(1)网络范围无限大，忽略边际效应的影响；
(2)节点依照密度为λ的2维泊松点过程分布；
(3)MAC层接入协议使用IEEE 802.11 DCF；
(4)网络处于饱和条件下，每个节点在任何时候都有等待发送的分组；
(5)业务均匀，每个节点等概率地向其他所有节点发送，且业务量相同；
(6)所有节点拥有相同的传输半径R，节点的平均邻节点数量为n=λπR2；
(7)网络节点使用相同的路由协议，不考虑多种路由策略混合使用的问题。
一些研究多跳网络的工作中，使用节点的(一跳)吞吐量作为衡量网络性能的尺度。然而这一个适用于WLAN的指标，无法反应出多跳网络中的一些特性。在文献[2，3]中，使用了平均发送前进量为指标来衡量网络性能，较好地解决了这一问题。但由于这些文献是针对slotted ALOHA协议的网络，其定义平均发送前进量时用到的时隙概念并不适合IEEE 802.11 DCF的实际情况。因此，本文重新定义平均前进量为：在单位时间内，一个节点能够成功发送的分组数量与这些分组在前进方向上前进距离之积的期望值。该指标综合考虑了传输距离与传输成功率之间的折衷问题，显然该值越大，表明网络承载业务的能力越强。
2 数学分析模型描述
自从提出IEEE 802.11以来，对它的性能分析成为了研究焦点。其中，文献[7]开创性地使用基于Markov链的模型来描述[EEE 802.11 DCF所有的指数退避协议细节，构造单跳、全连通网络下的协议分析模型。由于该模型具有很好的结构和精确性，使得其后很多关于WLAN网络的研究主要基于该模型，并且产生了很多改进和变型的分析模型。
文献[10]在文献[7]的基础上进行改进，考虑了多跳环境下节点的空间分布、隐藏终端、空间复用等因素对分组传输成功概率的影响，使得该模型能够被用于进行多跳网络。本文在该模型基础上进行网络容量分析。该模型最终可表达为一个方程组，对其求解后可得到所有变量值，其中包括：变量τ，表示网络节点在一个空闲时隙内发送分组的概率；变量p，表示发送分组失败的概率；变量σ，表示网络节点监测到一次空闲时隙的平均时间间隔。模型推导过程不是本文主题，不再详述，仅解释其中与本文研究目标相关的几个重要控制参数(Γ，Λ1，Λ2)的物理意义。
如图2所示，文献[10]把接收节点的干扰区域中没有与发送节点干扰区域(即传输覆盖范围内)相交的部分称为“接收节点独占区”(简称B区域)，定义接收节点独占区中节点平均数量与干扰区域中邻节点总数之比为Γ。此外，文献[10]还定义了Λ1，表示在接收独占区域中任选一个节点的干扰区内，与发送节点S干扰区不相交部分的面积，相对于整个干扰区面积进行归一化的期望值；定义了Λ2，表示在接收独占区域中任选一个节点的干扰区中，与接收节点D干扰区不相交部分的面积归一化期望值。可以看出，分析模型中引入的几个控制参数取值与网络中节点分布特性和网络中采用的路由策略有关。由于文献[10]中没有给出这些控制参数的推导方法和表达式，本文首先对这方面的工作进行了补充。
3 分析模型控制参数与路由策略的关系
由于Ad Hoc网络中实际的路由协议很难使用数学方法进行描述，因此本文中采用了四种不同风格的路由策略代替实际的路由协议。
第一种路由策略是MFR(Most Forward withFixed Radius R)：在此策略下，当前发送节点在转发分组的时候，会选择在自己传输范围内，能在分组前进方向上造成最大前进距离的邻节点作为自己的下一跳转发节点。
其余三种是基于扇区限制的路由策略，分别为：NFPS(Nearest with Forward Progress in Sector)：在以前进方向为中心的一个角度为2φ大小的扇区内，发送节点选择距自己最近的邻节点作为自己的下一跳转发节点；FFPS(Furthest with Forward Progress in Sector)：在2φ扇区内，发送节点选择距自己最远的邻节点作为自己的下一跳转发节点；RFRS(Random Forwardwithin Radius R in Sector)：在2φ扇区内，发送节点选择自己传输范围内任意的一个邻节点作为自己的下一跳转发节点。概括而言，在这些策略中，NFPS所导致的最终路由为短跳路由，MFR及FFPS为长跳路由，RFRS特性介于以上三者之间。
在上述四种路由策略下，发送节点与接收节点之间的位置关系特性不同。在图3中，将接收节点相对于发送节点的位置用极坐标(r0，θ0)表示。其中，坐标原点为发送节点，极坐标方向为数据分组的前进方向，显然r0与θ0是随机变量，而它们的统计特性与网络中使用的路由策略有关。可以使用r0与θ0的联合分布密度函数fr0，θ0，靠(r0，θ0)来描述它们的统计特征。由于篇幅限制，推导过程略。
在MFR路由策略下，(r0，θ0)的联合分布密度函数如下：
在NFPS策略下，(r0，θ0)的联合分布密度函数如下：
在FFPS路由策略下，(ro，θ0)的联合分布密度函数表达式如下：
在RFRS路由策略下，(r0，θ0)的联合分布密度函数为：
在此基础上结合图4，推导出分析模型控制参数的表达式如下：
至此，完成对分析模型中控制参数的推导。这些控制参数的取值反映了发送节点和接收节点之间的位置关系特性，它们影响着分析模型最终的计算结果(如：p，τ，σ等)。在计算出各个控制参数的值后，将其代入到分析模型的方程组中，就可以进行求解。
4 计算结果
现在，可以借助数学模型方法来分析网络中路由策略选择以及节点传输半径设置对网络容量的影响。研究对象是无限大均匀网络，节点分布密度为10-4节点／m2。其他条件见本文中网络条件部分的介绍。按照前面的叙述，采用节点平均发送前进量作为衡量指标，依照分析模型中定义的符号，可将其表示为：
式中：r为网络节点的传输半径设置。可以证明，对于任何密度的网络，z(r)随着网络中平均邻节点数变化的规律是相同的(仅相差常数倍)。因此传输半径的设置问题也可以等价为如何调整网络节点的邻节点数目，以使Z(r)指标最大。借助于Matlab 6.5数学工具，可以计算出在不同路由策略下Z(r)随着节点传输半径变化的规律，如图5所示。
从图5中可以看到，在网络节点密度一定的情况下，节点的平均发送前进量指标随着节点传输半径的增加而单调下降。这意味着在使用IEEE 802.11 DCF为MAC层接入协议的多跳网络中，减小节点的传输半径对于提高网络容量是有利的。由于在实际网络设计时还要考虑网络的连通性问题(过小的传输距离设置将导致网络出现分离)，所以在保证网络连通条件下尽量减小节点的传输半径是一个最优策略。
此外，在网络节点传输半径一定的条件下，不同的路由策略也会造成节点平均发送前进量指标变化。从图5中可以看到，NFPS路由策略下，节点发送前进量指标最差。而MFR路由明显优于其他三者。这一结果说明，在节点传输半径一定的条件下，网络中使用能够导致最大分组前进距离的路由策略对于提高网络容量是有利的。
5 结 语
本文使用数学分析的方法研究了基于IEEE 802.11DCF的无线多跳网络中传输半径设置问题和路由方案选择问题。使用分析模型计算出的结果表明，在节点分布密度一定的条件下，网络中的节点平均发送前进量随着传输半径的增加而单调下降。这说明在保证网络连通性的条件下，减小节点的传输距离有利于增加网络的容量。而在传输半径一定的条件下，使用能够导致更大前进距离的路由策略对于提高网络容量有利。
对于Ad Hoc或传感器网络这样的多跳无线网络来说，信源节点与信宿节点通常不在对方的传输覆盖范围内，因此在传送信息时需要经过中间节点的转发。在转发过程中，对路由的选择可以有两种策略：短跳路由策略，即数据转发过程使用由多个短距离链路组成的路由；长跳路由策略，即数据转发过程使用由少量的长距离链路组成的路由。
不同路由策略对网络传输容量带来的影响是一个值得关注的问题。对此，一些研究给出了不同的观点。文献[1]认为在一个干扰受限的网络中，每跳的距离越短，网络的传输容量越高。文献[2-4]则从分析网络干扰的角度，研究了长跳／短跳路由问题，认为网络中可能存在一个最佳的传输半径设置，能够使网络的容量达到最大。尽管这些文献的观点并不相同，但是它们之间并不存在直接的对立，原因是它们所假设的网络条件不同(其中，最主要的是网络中MAC协议的差别)。笔者认为，对于网络性能所进行的分析应根据实际的网络条件来进行，不存在普遍适用的准则。
在多跳网络中，路由协议和MAC协议的互动会对网络性能产生很大的影响，因此将这两个层次的技术结合起来进行性能分析是必要的。近年来，IEEE 802.11已经成为无线局域网中一个主要的国际标准，其中基本的接入机制是分布式协调功能(DCF)。随着Ad Hoc网络技术在军事、商业等领域的应用，IEEE 802.11DCF作为主流接入协议之一受到了更多关注，因此本文研究的多跳网络则基于这种MAC协议。使用数学分析方法，研究了在IEEE 802.11 DCF多跳网络中，路由策略和节点传输半径设置对网络容量的影响问题。
1 路由特性对多跳网络容量的影响
在多跳网络中主要有两种不同的因素会对最终生成的路由长跳／短跳特性产生影响：
(1)节点功率(传输半径)设置的影响
如果节点功率设置较低，传输距离较短，必然会造成传输路由为短跳路由。这会对网络容量带来双重影响，有利的方面包括：小的传输距离意味着信道的空间复用能力提高，网络中可以有更多的传输同时发生；节点传输范围内的平均邻节点减少，由于分组碰撞而导致传输失败的概率减小。不利的方面则是：分组需要更多的跳数才能到达最终的目的节点，传输过程中出现失败而丢弃分组的概率增加；为完成同样数量的端到端业务传输，网络节点的平均转发次数增加，致使网络内部更加繁忙。这在一定程度上抵消了由于空间复用能力增加而带来的好处。如果节点功率设置较高则情况相反。
(2)路由策略的影响
在网络节点功率设置确定的情况下，不同的路由策略也会造成最终生成的路由特性不同。倘若发送节点使用的路由协议(或策略)倾向于选择距离自己近的邻节点作为下一跳的转发节点，则最终生成的路由必然是短跳路由。反之，则会导致长跳路由。
路由协议对网络性能的影响可参照图1来说明：在多跳网络中，基于载波监听的MAC协议(如：IEEE 802.11 DCF)都需要面对隐藏终端问题。当节点S发起传输后，处于节点D独占区(用B(S，D)表示)的节点无法监听到节点S的信号，因此可能在此次传输进行期间发起新的干扰传输，造成S，D之间传输失败。显然，B(S，D)区域的面积越大，隐藏终端的数量越多，传输失败概率也就越大。然而，B(S，D)区域的面积大小则受到路由策略的影响。
基于以上原因，在多跳网络中，对于MAC层性能的研究应结合特定的路由策略以及功率控制方案来进行才更有意义。此外，虽然路由策略和节点功率设置都可能造成路由的短跳／长跳特性变化，但是这两种因素对网络性能的影响机制是有差别的。例如：当节点的发送功率确定时，改变路由策略可以造成路由长跳、短跳的特性不同，但通常对网络中信道的空间复用能力没有影响。在进行研究时，应该对这两种因素的影响进行区分。
本文所进行的研究，基于如下的网络条件假设：
(1)网络范围无限大，忽略边际效应的影响；
(2)节点依照密度为λ的2维泊松点过程分布；
(3)MAC层接入协议使用IEEE 802.11 DCF；
(4)网络处于饱和条件下，每个节点在任何时候都有等待发送的分组；
(5)业务均匀，每个节点等概率地向其他所有节点发送，且业务量相同；
(6)所有节点拥有相同的传输半径R，节点的平均邻节点数量为n=λπR2；
(7)网络节点使用相同的路由协议，不考虑多种路由策略混合使用的问题。
一些研究多跳网络的工作中，使用节点的(一跳)吞吐量作为衡量网络性能的尺度。然而这一个适用于WLAN的指标，无法反应出多跳网络中的一些特性。在文献[2，3]中，使用了平均发送前进量为指标来衡量网络性能，较好地解决了这一问题。但由于这些文献是针对slotted ALOHA协议的网络，其定义平均发送前进量时用到的时隙概念并不适合IEEE 802.11 DCF的实际情况。因此，本文重新定义平均前进量为：在单位时间内，一个节点能够成功发送的分组数量与这些分组在前进方向上前进距离之积的期望值。该指标综合考虑了传输距离与传输成功率之间的折衷问题，显然该值越大，表明网络承载业务的能力越强。
2 数学分析模型描述
自从提出IEEE 802.11以来，对它的性能分析成为了研究焦点。其中，文献[7]开创性地使用基于Markov链的模型来描述[EEE 802.11 DCF所有的指数退避协议细节，构造单跳、全连通网络下的协议分析模型。由于该模型具有很好的结构和精确性，使得其后很多关于WLAN网络的研究主要基于该模型，并且产生了很多改进和变型的分析模型。
文献[10]在文献[7]的基础上进行改进，考虑了多跳环境下节点的空间分布、隐藏终端、空间复用等因素对分组传输成功概率的影响，使得该模型能够被用于进行多跳网络。本文在该模型基础上进行网络容量分析。该模型最终可表达为一个方程组，对其求解后可得到所有变量值，其中包括：变量τ，表示网络节点在一个空闲时隙内发送分组的概率；变量p，表示发送分组失败的概率；变量σ，表示网络节点监测到一次空闲时隙的平均时间间隔。模型推导过程不是本文主题，不再详述，仅解释其中与本文研究目标相关的几个重要控制参数(Γ，Λ1，Λ2)的物理意义。
如图2所示，文献[10]把接收节点的干扰区域中没有与发送节点干扰区域(即传输覆盖范围内)相交的部分称为“接收节点独占区”(简称B区域)，定义接收节点独占区中节点平均数量与干扰区域中邻节点总数之比为Γ。此外，文献[10]还定义了Λ1，表示在接收独占区域中任选一个节点的干扰区内，与发送节点S干扰区不相交部分的面积，相对于整个干扰区面积进行归一化的期望值；定义了Λ2，表示在接收独占区域中任选一个节点的干扰区中，与接收节点D干扰区不相交部分的面积归一化期望值。可以看出，分析模型中引入的几个控制参数取值与网络中节点分布特性和网络中采用的路由策略有关。由于文献[10]中没有给出这些控制参数的推导方法和表达式，本文首先对这方面的工作进行了补充。
3 分析模型控制参数与路由策略的关系
由于Ad Hoc网络中实际的路由协议很难使用数学方法进行描述，因此本文中采用了四种不同风格的路由策略代替实际的路由协议。
第一种路由策略是MFR(Most Forward withFixed Radius R)：在此策略下，当前发送节点在转发分组的时候，会选择在自己传输范围内，能在分组前进方向上造成最大前进距离的邻节点作为自己的下一跳转发节点。
其余三种是基于扇区限制的路由策略，分别为：NFPS(Nearest with Forward Progress in Sector)：在以前进方向为中心的一个角度为2φ大小的扇区内，发送节点选择距自己最近的邻节点作为自己的下一跳转发节点；FFPS(Furthest with Forward Progress in Sector)：在2φ扇区内，发送节点选择距自己最远的邻节点作为自己的下一跳转发节点；RFRS(Random Forwardwithin Radius R in Sector)：在2φ扇区内，发送节点选择自己传输范围内任意的一个邻节点作为自己的下一跳转发节点。概括而言，在这些策略中，NFPS所导致的最终路由为短跳路由，MFR及FFPS为长跳路由，RFRS特性介于以上三者之间。
在上述四种路由策略下，发送节点与接收节点之间的位置关系特性不同。在图3中，将接收节点相对于发送节点的位置用极坐标(r0，θ0)表示。其中，坐标原点为发送节点，极坐标方向为数据分组的前进方向，显然r0与θ0是随机变量，而它们的统计特性与网络中使用的路由策略有关。可以使用r0与θ0的联合分布密度函数fr0，θ0，靠(r0，θ0)来描述它们的统计特征。由于篇幅限制，推导过程略。
在MFR路由策略下，(r0，θ0)的联合分布密度函数如下：
在NFPS策略下，(r0，θ0)的联合分布密度函数如下：
在FFPS路由策略下，(ro，θ0)的联合分布密度函数表达式如下：
在RFRS路由策略下，(r0，θ0)的联合分布密度函数为：
在此基础上结合图4，推导出分析模型控制参数的表达式如下：
至此，完成对分析模型中控制参数的推导。这些控制参数的取值反映了发送节点和接收节点之间的位置关系特性，它们影响着分析模型最终的计算结果(如：p，τ，σ等)。在计算出各个控制参数的值后，将其代入到分析模型的方程组中，就可以进行求解。
4 计算结果
现在，可以借助数学模型方法来分析网络中路由策略选择以及节点传输半径设置对网络容量的影响。研究对象是无限大均匀网络，节点分布密度为10-4节点／m2。其他条件见本文中网络条件部分的介绍。按照前面的叙述，采用节点平均发送前进量作为衡量指标，依照分析模型中定义的符号，可将其表示为：
式中：r为网络节点的传输半径设置。可以证明，对于任何密度的网络，z(r)随着网络中平均邻节点数变化的规律是相同的(仅相差常数倍)。因此传输半径的设置问题也可以等价为如何调整网络节点的邻节点数目，以使Z(r)指标最大。借助于Matlab 6.5数学工具，可以计算出在不同路由策略下Z(r)随着节点传输半径变化的规律，如图5所示。
从图5中可以看到，在网络节点密度一定的情况下，节点的平均发送前进量指标随着节点传输半径的增加而单调下降。这意味着在使用IEEE 802.11 DCF为MAC层接入协议的多跳网络中，减小节点的传输半径对于提高网络容量是有利的。由于在实际网络设计时还要考虑网络的连通性问题(过小的传输距离设置将导致网络出现分离)，所以在保证网络连通条件下尽量减小节点的传输半径是一个最优策略。
此外，在网络节点传输半径一定的条件下，不同的路由策略也会造成节点平均发送前进量指标变化。从图5中可以看到，NFPS路由策略下，节点发送前进量指标最差。而MFR路由明显优于其他三者。这一结果说明，在节点传输半径一定的条件下，网络中使用能够导致最大分组前进距离的路由策略对于提高网络容量是有利的。
5 结 语
本文使用数学分析的方法研究了基于IEEE 802.11DCF的无线多跳网络中传输半径设置问题和路由方案选择问题。使用分析模型计算出的结果表明，在节点分布密度一定的条件下，网络中的节点平均发送前进量随着传输半径的增加而单调下降。这说明在保证网络连通性的条件下，减小节点的传输距离有利于增加网络的容量。而在传输半径一定的条件下，使用能够导致更大前进距离的路由策略对于提高网络容量有利。
下载文档
