论文研究-Ad Hoc网络中公平与效率兼顾的信道接入退避算法 .pdf

所需积分/C币:7 2019-08-17 00:21:10 312KB .PDF

Ad Hoc网络中公平与效率兼顾的信道接入退避算法,李广,,Ad Hoc网络中的媒体接入控制协议的性能是决定节点能否高效、公平地共享有限带宽资源的主要因素。基于网络局部通信状况估计思想,提
山国武技论文在线 http://www.paper.edu.cn 节点次竞争成功后退避时问设置较长,尽量保证节点间信道竞争的公平性:在全网络其它 通信较闲区域,节点问信道竞争发生冲突的可能性不大,此时节点一次报文传输成功以后退 避时间设置较短,尽量使得节点在单位时间内能够发送更多的报文,以增加全网的吞吐量, 提高网络数据传输效率 21算法的基木描述 如何简单估计节点周闱的通信状况而不増加额外的网络传输负担呢?算法的解决办法 是设定一个退避次数计数器N,节点在信道竞争中每冲突一次N就增加1,只到信道竞争成 功或者超过协议设定的最大重传次数丢包。在下次重新设定窗口大小的时候,根据N的值 来设定个同大小的窗口。N的值大,认为该节点处于节点密度大、恻络通信忙区域,退避窗 口设定为较大值,一方面能够降低木节点下一次信道竞争时发生冲突的概率,另一方面使得 该区域内的其它节点在下次竞争中具有相对优势,照顾到了节点信道竞争的公平性;N的 值小,认为节点正处于节点密度小、网终通信闲区域,退避窗口设定为较小值,这样节点的 退避时间短,节点能够在单位时间内发送更多的数据包,提髙了网络的数据传输吞吐量。同 时这也与信道竞争的公平性没有冲突,由于该区域节点密度小,信道竞争发生冲突的可能性 本来就低。 下述的公式(4)描述了本算法: Finc= Min(2*CW-1, CW max) Fde= Max(2-1,CW min)OsNSN 4) CH max No 其中t与N为两个可选择参数,在小业务量网络中可选择较小的t与M,在大业务量 网络中可选择较大的t与Nn,一般情况下t的取值为16至64,N为3至6。算法中t与Nn 的选择是本算法的关键,它的选择直接关系到整个网络的性能,对于特定的网络拓扑结构 通过分析和仿真比较可以选择最优的t与N的值 22退避时间计算 对于大多数 Ad Hoc网络MAC协议的退避算法来说,其退避时间都可以用下式来表示: BackoffTime= Random0*a SlotTime (5) 其中, Random0为一个分布在[0CW区间内的伪随机数。CW为竞争窗口,且 CWmin<CW< WImax,其中BEB算法中 CWmin默认值为31, CWmax默认值为1023。 aSlotTime为物理层管理信息厍(MB)中所取的值,默认值为20us。在大多数改进退避算法 的文献中般都只改进了CW的取值方式,然而从上述退避时间的取值方式上分析我们不 难得知这样的方式是有明显的缺陷的。例如当节点在一次竞争信道的过程中需要有较长的退 避时间,此时退避算法一定会设定较大的竞争窗口CW值,然而由于退避时间是在[0CW] 上随机取值,此时仍然有可能取到靠近0的一个较小的值,这样就与算法的本意产生了矛盾。 因而为了使退避时间与窗口大小的取值基本同步,我们也有必要对上述退避时间与退避窗口 之间的取值关系做出改进。 山国武技论文在线 http://www.paper.edu.cn 参考文献[2],在退避吋间的计算上,我们按如下的公式来进行: T=Random cw (6) BackotfTime=Ts aslot time 在节点退避时间与退避窗口变化基木一致的原则下,公式(6)里的 Random取值不再是区 间[0,CW内的伪随机数,而是区间[0.95,105]内的伪随机数。之所以在这里将退避时间 Backofffime随机化,主要是为了避免同一区域内两节点的退避时间相同而增加信道竞争冲 突的可能性 23公平性指数 为了衡量一种退避算法对节点信道接入公平性的影响,文献[10]提出了公平性指数 ( Fairness index,缩写为FI),其定义为网终中最大链路昋吐量和最小链路昋吐量的比值 Fl Throughput Throug hput min 显然,FI=1是最小值(理想情况),即每个链路具有相同的吞吐量,公平地分配信道 资源。H越大,节点竞争信道能力悬殊越大,不公平性就越明显。 与外,也有研究者提出用改进的公平性指数( Improved Fairness Index,缩写为IFI)衡 量算法的公平性,如下式 ⅠF Throughput max- Throughput min (8) Throughputiotal 在公式(8)下,IFI=0为最小值(理想情况),此时每个链跻具有相同的吞吐量,公平 地分配信道。然而公式(7)与(8)具有明显的缺陷,单从网终最大链路昋吐量和最小链路 吞叶量来衡量节点链路信道竞争公平性不能完全反映整个网络的公平性情况,因而得到的结 果也背定不准确。设有如下两组吞吐量:其中组一{0.0.0.2,0.4,0.6,0.8,1,00}、组二 0.0.0.1,0.3,0.7,0.9,10},很明显组一中的节点信道竞争公半性要好于组二,但是通过公式(7) 汁算出来的结果两组情况均为无穷大,根木无法比较;通过公式(8),两组计算的结果均 为2.00,也无法比较哪组吞吐量的公平性更好。 借鉴薮理统计中标准差概念,提岀了·种能反映全网所有链路信道竞争公平性指数计算 方法( Fairness index of all! Links,缩写为FIAL),如下式: FIAL=.s(Throughput, -Throughput)? (9) Throughput 显然,用公式(9)来襖量节点信道接入公平性更合理,其中公式中 Throughput;为网络中第 i条链路的吞吐量, Throughput为网络中所有链路吞吐量的平均值,N为链路数。HAL=0 为最小值(理想情况),且FIAL值越小,说明各节点在信道竞争公平性表现越好。利用该 山国武技论文在线 http://www.paper.edu.cn 计算方法,我们可以很容易计算出上述组·吞吐量的FIAL=1673,组二吞吐量的 FIAL=1.897,说明组一吞吐量在公平性方面表现更优秀,这与我们的直观评价是一致的。 3.BFAE算法性能分析与实验仿真 3.1算法的马尔可夫链模型分析 参考义献[12]我们假设每个数据包在传输过程屮均有一个相互独立且恒定的冲突概率 ,当BFAF算法参数1为32,M为5时,假设s)与b(t)分别为退避过程中每一退避阶段 的重传级数与退避窗口值,可得出一个马尔可夫链来描述这个二维离散时间随机过程 s(t),b(t)},该马尔可夫链非空一步转移概率如下式表示: p,kk+1=1 i∈[Q5从∈0.322-2 p2+132*21-;=Pi04 (10) pN,32*2-10=(-PCP(-P)i∈[05NEQ 在上式中:pi,k1i.k}=p(+1)=1,b(+1)=k1|()=1,b()= 考虑到退避窗口在[0.95,1,05区间小范围随机化只是为了减小同一区域两节点冲突概率 而基本不影响算法退避时间的大小,为简化分析,该马尔可夫链模型未考虑退避窗口在区间 [0.95,1,05]上的随机化。 1-P 0≤ Vs1 CP(1-P)2 ∠1 2 0≤N≤2CP(1-P3 2(20×1(21)…(2BX1(327 0≤≤3CP(1-P 3.25 0≤N≤4CP(-P 4,51I 0≤N≤5CP(- (5xm((52 5,1023 图1BFAE算法马尔可夫链模型 设bk= lim pse()=b()=k:∈0.5 为状态{s(t)b(t)}的稳态分布,根据马尔可大 t→ k∈[0,3282- 链模型状态图1可以得到如下的稳态分布方程: 山国武技论文在线 http://www.paper.edu.cn b0=b,ki∈[0,5]k∈[0,32*21-1] (1-P)"bm b0=P*b-0+∑CP(1-P)中i∈[15] 又有: 322Vk=1 (12) 根据方程组(11)与方程(12),可以得到b,ki∈[0.5],k∈[0,32*2-1]。对bk求和 可以得到时隙选择分布函数r(0≤:0≤32*2-1),其中z=∑bk 参考文献[12],饱和吞吐量S可表示如下:s FIP (13) Ts-TU (1-Pn)/P+7 P 其中EP为包平均有效载荷大小,T为报文一次传输成功后侦听信道忙的平均时间, T为一次冲突过程中侦听信道忙的平均时间,σ为一个空时隙持续时间,P为一个时隙中 数据包至少传输一次概率,P为信道中一次传输成功概率,且有下式: Pr=1-(1-z)”PS nz*(1-z) (14) 上式屮的n为网终节点总数,τ为任意一个随机时隙中节点的包发送概率,且τ 至此通过公式(13),我们可以计算BFAE算法下网终的饱和吞吐量S。 32算法仿真实验 本文选用NS( Network simulator,ns2.31)作为仿真平台。网络中一共有28个节点, 网络节点的设置与一般实际应用中的情况相一致,其中16个节点处于节点密度高区域,12 个节点处于节点密度低区域,相邻两节点的最小距离为250米,其中节点19与节点25、节 点2与节点22之间的距离为400米。节点发射功率采用NS2802.l1标准默认值,在此默认 值下,节点传送/接收距离是250米/550米。网络的拓扑结构如下图2 数据业务类型釆用CBR( Constant Bite rate),在仿真过程中以恒定速率持续发送数据, 仿真时间为50S,数据报文长度从25字节到500字节变化,数据报文发送时间间隔从0.01S 到0.03S变化。 为充分体现冬协议特点,仿真时的小业务量模型下的BFAE协议t参数取为16,排队 接入算法的参数BW取为50;人业务量模型下BFAE协议t参数取值为32,排队接入算法 的参数BW取为150。BFAE算法中M值取为5。在MILD算法中a参数取值为2,b参数 取值为1,其它参数均为标准802.11BEB下的默认值 山国武技论文在线 http://www.paper.edu.cn ⊙○③ 图2仿真实验网络节点拓扑图 在图3至图6中,数据包发送时间间隔为0.01S,图7与图9中数据包大小为175字节, 图8与图10中数据包大小为375字节。 throughput(Mbps) throughput(Mbps MILD21 MILD21 3.2 B=AE52 18·BFfe 1.6 F'queue5C" 1,2 0.8 4 the size of packet(Byte) the size of Facket(Byte) 图3包大小与吞吐量关系 图4包大小与吞吐量关系 如图3、图4所小,在小业务量数据吞吐量方面,除MILD协议表现较差外,其余三种 协议表现相当。这主要是因为在浏终数据业务量较小时,树络处于轻负荷状态,各节点之间 数据包椪撞的可能性较小,信道接入退避算法对网络吞吐量的影响较小。在大业务量数据模 型情况下,BFAE算法表现仅稍逊色于BEB算法,而明显优于其亡两种算法。这种结果乜 是可以预期的,因为在BEB算法中,每次节点信道竞争成功其退避时间就减为最小,这样 在全网络来考虑,其吞吐量一般情况下表现是最好的,但BEB算法却牺牲了公平性指数和 云包率等其它重要网络性能指标。 从图5、图6中我们可以看到,在节点信道接入公平性方面BFAF算法与其它三种算法 相比具有明显优势。同时BFAE协议在不同数据业务模型下的曲线最为平缓,说明该算法具 有更好的网络应用适应性。 7 山国武技论文在线 http://www.paper.edu.cn airness Index(FIAL) Fairness Index(FIAL) CEEB feb" MilIZ "MILI21" 3 BFFE32 BFFE16 2.5 15 250 the size of packet( Byte) the size of 图5包大小与公平性指数关系 图6包大小与公平性指数关系 图7、图8说明,在这种网终数据业务模型下,BFAE算法在吞吐量方面的表现与理论 分析最优的BEB算法表现相当,同时曲线整体也呈下降趋势。 图9、图10明显显示出BFAE在节点信道接入公平性方面相比其它三种算法的优势, 并且曲线随着包发送间隔时问的增加而呈卜降趋势。 MILD21 MILI21 RFAF16 " BFAE32 q50 qucue150 1.3 1.8 12 0.010.0120.0140.0160.0180.020.0220.02400260.0280.03 0,010,020.0140,0160,0100,020,0220,02400260,0280,03 packet interval time(s) packet interval time(S) 图7包发送时间间隔与春吐量关系 图8包发送时间间陶与吞吐量关系 Fairness Index(FIAL) Fairness Index(FIAL) "MILI21" MILD21 BFFE32 EFAE16 1.5 1 0.5 0 0.010.0120.0140.0160.0180.020.0220.0240.0260.028003 0010.0120.0140.0160.0180.020.0220.0240.0260.0280.03 packet interval time(S) packet interval time(s) 图9包发送时间间隔与公平性指数关系图10包发送时间间隔与公平性指数关系 综合图7至图10,很容易得到如下结论:公平性指数与网络吞吐量指标是相互制约和 影响的。在具体的网络应用背景下,在BFAE算法中选择合适的t值与N值可以使得BFAE 算法在尽可能保证网络高吞吐量的前提下,改善网络节点信道接入竞争的公平性。 山国武技论文在线 http://www.paper.edu.cn 结论 在AdHo网络中,信道接入的公平性与网络吞吐量是信道接入退避算法的主要研究对 象。本文在分析现有主要几种退避算法后提岀了一种效率与公平兼顾的退避算法,并且提出 了一种准确评价全网信道接入公平性的信道接入公平性指数计算方法。通过木文分析与仿真 实验结果表明,与现有其它几和常见算法枏比,本算法不给网络通信带来额外的报文传输负 担,并且在争取网终最人昋吐量的基础上,实现了网络各节点公平地信道接入。 参考文献 l]郑少仁,王海涛赵志峰等. Ad hoc网终技术[M]北京:人民邮电出版社,2005,1-5) 「2吴传霞,范平志,冯军焕.一种 Ad hoc网络信道接入排队退避公平算法门J.系统仿頁学 报,2004.16(5):111114 [3 IEEE Std. 802.11-1997, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer(PHY) specifications[s].http://www.ieee.org [41 V Bharghavan, A Demers and SShenker. MACAW: A Media Access Protocol for Wireless LANs [C].In Proceedings of ACM SIGiCOMM94 1994.212-225 [5]BNBhandari. R.V. Raja Kumar, S L Maskara. A Modified Back-off Algorithm for the IEEE 802. 11 dCF 刂」.FE(S424440),205:51-54 [6 Jenhui Chen, Wenchiao Wu Dynamic Contention Window Selection Scheme to Achieve a Theoretical Throughput Limit in Wireless Networks: A Fuzzy Reasoning Approach []. IEEE (S7803-8521) 2004:3196-3120. I7 LI YUN, LONG KE-PING, ZHAO WEI-LIANG and CHEN QIAN-BIN. A Novel Random Backoff Algorithm to Enhance the Performance of IEEE 802.11 CF IC]. Wireless Personal Communications(2006)36: 29-44 [8] I-Hung Lin, Jen-Yi Pan. Throughput Analysis of a Novel Backoff Algorithm for IEEE 802.11 WLANS J. IEEE Wireless Telecommunications Symposium(S7803-8856). 2005: 85-90 [9] Raffaele Bruno, Marco Conti, Enrico Gregori, Romano Fantacci. Throughput vS. Temporal MAC protocols in Multi-Rate WLANS: Analysis and Performance Evaluation [IEEE (S7803-8255) 2004:2017-2021 [101 T. ozugur, M Naghshineh, P Kermani, and J. A Copeland, Fair Media Access for Wireless LANSC. Proceedings of IEEE GLOBALCOM99.1999, 570-579 [I1]李瑞芳,李仁发. Ad Hoc网络信道接入退避算法研究科学技术与工稈[门.2006,15(6):2358-2363. [12] G Binachi, Performance Analysis of the IEEE 802. 11 Distributed Coordination Function [C], IEEE Journal on Selected Areas in Communication, Vol 18, No 3, pp. 535-547, March 2000 [13NetworkSimulatorns-2[eb/ol].http://www.isi.edu/nsnam/ns [14 WU Chuan-xia, FAN Ping-chi, FENG Jun-huan On a Queue Backoff Fair Algorithm for Channel Access in Ad Hoc Nctwork [] Journal of Systcm Simulation(S1004-731x), May 2004: 1111-1114 a Fair and efficient Channel Access Backoff Algorithm in Ad hoc Li Guang School of Information Engineering, Wuhan University of Technology, Wuhan, (430070) Abstract The performance of media access control protocol in Ad Hoc network is the major factor to determine whether the nodes can efficiently and fairly share the limited channel resource or not. Basing on communication status estimating idea of local area network, it puts forward a fair and efficient backoff algorithm in nodes channel competition and evaluates the fairness of node channel competition by calculating the fairness index for channel competition of all network links. The analysis and the result of stimulation experiment show that comparing with the standard beb algorithm in IEEE 802. 11 and other algorithms, the algorithm is not only simple, but also has an excellent performance in fairness of node channel competition under the circumstances of a high throughput of the network Keywords: Ad Hoc network; backoff algorithm; fairness index; MAC protocol 9

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐