IEEE802.11DCF机制的三维Markov模型分析与仿真.pdf

《IEEE802.11DCF机制的三维Markov模型分析与仿真.pdf》由会员分享，可在线阅读，更多相关《IEEE802.11DCF机制的三维Markov模型分析与仿真.pdf（4页珍藏版）》请在三一文库上搜索。

1、第 l 9卷第 7期 2 0 0 9年 7月 计 算 机 技 术 与 发 展 C OMP UTER TECHNOL( Y AND DF VEL0P M叵NT 、 ， o 1 1 9 No 7 J u 1 2 0 0 9 I E E E 8 0 2 1 l D C F机制的三维 Ma r k o v模型分析与仿真 董明忠 ( 昆明理工大学， 云南 昆明 6 5 0 0 9 3 ) 摘要： I E l F S 0 2 1 1 分布式协调机制( DC F ) 是颇具影响力的无线网络标准， 协议基于载波检测 碰撞退避多址接人协议和 时隙退避算法。针对 I E E F S 0 2 I I I F饱和状态

2、不能解决无线网络复杂的工作机制 ， 提出三维 Ma r l v 链 ( 3 M) 模型， 分析 I I F P R 0 2 1 l D C F的非饱和性能， 各站点在发送成功后随机产生新的数据分组 ， 且到达率满足 P o i s s o n 分布。三维 Ma r k o v 模型的仿真与理论分析吻合 ， 这表明 3 M对系统的吞吐率 、 延迟性能、 稳定性等参数有明显的提高与改善。 关键词： 卿0 2 1 1 D C F ； 三维 Ma r k o v 模型 ； 非饱和 中图分类号： T P 3 9 1 9 文献标识码 ： A 文章编号： 1 6 7 3 6 2 9 X ( 2 0 0 9

3、) 0 7 0 1 5 2 0 4 An a l y s i s a nd S i mu l a t i o n I EEE80 2 1 1 DCF M e c h an i s m Ba s e d o n Thr e eDi me n s i o na l M a r k o v M o de l D ONG Mi n g z h o n g ( Ku n mi n g Un i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y ， K u n mi n g 6 5 0 0 9 3 ， C h i n a ) A lt r

4、a e t ： mE E 8 0 2 1 1 d i s t r ib u t e d c o o r d i n a t i o n me c h a n is m ( D C F )i s a c o n s id e r a b le i n i l u e n e e in t h e wi r e l e s s U s t a n d a r d s A g r e e n n t o n c a _r T i t“ d e t e c t i o nmu l t i p le a e o ns p r o t o c o l a n d giv in g t he c o ll

5、is i o n s lo t b a c k o f f a lg o r i t h m I EEE8 O 2 1 1 DCF s a t u r a t e d wi r e l e s s n e t wo r k t O s o l v et h i s l e v yc o mp le xm e c h a n is m。 3一DMa r k o v c h a i n( 3 M) mo d e 1 I E E E 8 0 2 1 1 D C F a n a l y s e t h ep r o p e r t i e s o f u n s a t u r a t e d Af

6、t e r t h e s I N e s s o ft h et r a ns mi s s i o n s tat n sin a r a n d o ml yg e n e r a t e dn e w d a t aa n dme e t t h e p o i s z o nd is t r i b u t i o n a r r i v a l r a t es S i mu l a t io n a n dt h e o ， r e t i c a l a n a l y s i s o f t h r e ed k n e n s k ml Ma r k o v mo d e

7、l ，wh i c h s h o ws t h e t h r o u g h p u t o f小e s y s t e m 3 M d e l a y p e r f D r ma n c e p a r a me t e r s s u c h a s ama r k ed h np rov e me n tin s t a bil i t y a n d n p rov e me n t Ke y wo lfd s ： 麟0 2 1 1 DCF： t h r e edime n s ion a l M a r k o v mo d e l ； u n s a t u r a t ed

8、 O 引 言 众多协议无 线 网协议都 是在 I E E E 8 O 2 1 1 Dn F的 框架下进行研究， 如公平性 、 T C P性能、 冲突避退、 隐 藏和暴露终端等问题 】 。I E E E 8 0 2 1 l D C F E J 基本介 质访问控制机制， 提供异步的数据服务。基于 C S MA C A的 I E E E 8 0 2 1 l D C F ， 它具有两种介质访问模式： 基 本访 问模式 ( b a s i c a c c e s s me t h o d ) 和 可选 的 r s C T S ( r e q u e s t t o s e n d c l e a r t

9、 o sen d ) 访问模式。 文献 2 ， 3 为了分析 I E E E 8 0 2 1 1 D C F的饱和吞 吐率， 假设在理想信道 ( 没有隐藏节点或独占信道现 象) ， 有固定数 目的节点 ， 且每个节点总是有数据包要 发送 ， 首先针对每一个单一的节点， 根据指数退避机 收稿 日期： 2 0 o 8一o 9 2 6 ； 修回 日期 ： 2 o o 8一l 2 3 0 基金项 目： 云南省教育厅科学研究基金项 目( 5 Y 0 6 4 7 D) ； 昆明金汇通 无线与微波技术研究所横向基金项 目( K MI I T I 2 0 0 6 0 0 1 2 ) ； 云南省无 线电管理委员

10、会横向基金项 目( YNR 2 0 0 7 0 1 4 ) 作者简介： 董明忠( 1 9 7 2 一) ， 男 ， 副教授， 硕士， 主要研究方向为网络 协议与信息安全、 嵌入式电子产品开发。 制 ， 建立二维Ma r k o v 模型， 其思想是 ： 该节点在任意选 取的一个时隙内发送的稳态概率 r， 此概率不依赖于 所使用的访问模式( 即基本访问模式或 R T S C T S访 问模式) ， 而且发生在任意选取的一个时隙内的事件， 将吞吐率表示为概率 r的函数。H a i t a o Wu 1 J 等人对 B i a n c h i 的模型进行 了改进 ， 考虑 了重传次数限制， 即 重传

11、次数达到最大限制的阈值时， 当前数据包将被丢 弃， 竞争窗口将被重置为最小竞争窗 口大小。B i a n c h i 和 H a i t a o Wu的 Ma r k o v 模 型都 没有考 虑退避 过程 中 的冻结状态， 而且都是只分析了 D C F在饱和负载情况 下的吞吐率性能， 并没有分析介质访问延迟。 文中提出三维离散马尔可夫模型是基于非饱和状 态下的系统分析， 对 I E E E 8 0 2 1 l D C F机制进行建模仿 真。所谓非饱和状态是指 ， 各站点在成功发送数据后， 依据泊松分布随机产生新的数据分组。 1 三维 Ma r k o v 模型理论 假设某个 A d HO c

12、 网络包含 ， z 个站点： 各站点在成 第 7期 董明忠： I E E E 8 0 2 I I D C F机制的三维 Ma r k o v模型分析与仿真 1 5 3 功发送数据后 ， 随机产生新的数据分组 ， 新分组的到达 服从 P o i s s o n 分布 ， 平均分组到达率为 = 。 首先， 分析某个站点竞争信道的过程。令 r ( ) 表 示： 在时刻 t 该站点发送缓冲区中是否包含数据。 如果 没有数据， 则 r ( t ) =0 ， 该站点空闲； 如果包含数据， 则 r ( t ) =1 ， 该站点竞争信道。 令 S ( t ) 表示： r ( t )=1 时， 该站点在时刻 t

13、 退避级数， 取值范围为 0 ， m ； b ( t ) 表 示： r ( t ) =1 时， 该站点的退避时隙计数器在时刻 t 的 取值， 取值范 围为 0 ， 一1 ， w = 2 J Wo ， w0= c wra i n , 0 ， 优 。 显然， ， - ( t ) 、 5 ( t ) 和b ( t ) 分别描述 的三个随机过程 r ( f ) ， 5 ( t ) ， 6 ( f ) 来描述该站点竞 争信道的过程， 如图1 所示。 由于时隙A l o h a 的作用， 假 定各站点每次发送数据帧时， 数据帧的碰撞概率与过 去的碰撞次数无关 ， 即碰撞概率 P恒定 而且相互独立 。 这个

14、三维随机过程在时刻 r +1 的状态 r ( t+1 ) ， s ( r +1 ) ， 6 ( t +1 ) 只与前一个时刻 t 的状态 r ( t ) ， s ( t ) ， b ( t ) 有关， 与时刻 t 以前的状态， 如 r ( t 一1 ) ， s ( t 一 1 ) ， b ( t一1 ) 等无关， 而且 ， 状态和时间都是离散的。 所以， 随机 过程 r ( t ) ， s ( t ) ， 6 ( t ) 是三维 Ma r k o v ( 3 M) ， 如图 1 所示 。 P 1 ， ， 是I 1 ， ， 0 =P 0 南 Wm一1 ( 4 ) P 0 ， 0 ， 0 I 1

15、， ， 0 ：1 一P 0 J m ( 5 ) P ( 0 ， 0 ， 0 1 0 ， 0 ， 0 ) = ( 6 ) P 1 ， 0 ， k 1 0 ， 0 ， 0 = ( 1 一 ) Wo 0 k wo 一 1 ( 7 ) 其中， 式( 2 ) 表示， 在退避过程中， 退避计数器在 每个时隙的开始时刻减1 ； 式( 3 ) 表示， 当退避级数为 时， 如果发送失败， 退避级数加 1 ， 退避计数器的取值 等概率地从 0 ， + 1 1 选取； 式( 4 ) 表示， 当退避级 数 已经达到最大时 ， 如果 发送失败 ， 退避级 数不变 ； 式 ( 5 ) 表示， 站点将发送缓冲区内的分组成功

16、发送出去 后， 进入空闲状态； 式( 6 ) 表示， 如果没有新分组到达， 站点保持空闲； 式( 7 ) 表示， 如果新的分组进入发送缓 冲区， 站点进入退避过程， 退避级数为 0 ， 退避计数器 的取值等概率地从 0 ， o 一1 选取。 令 b =L i l n P r ( r ) ：i ， s ( t ) = ， b ( )：忌 ， 图 1 三维马可夫模型( 3 M) 为简化分析， 令 P i I ， J ， k 1 f i 0 ， J _ 0 ， k 0 f= 一f r ( t + 1 ) ：i l ， s ( t +1 ) =J l ， 1 p l 6 ( ， + 1 ) =k l

17、I r ( t ) = o ， s ( t ) = o ， 6 ( f ) =点 0 J ( 1 ) 由图 1 可知 ： PI 1 ， ， k i 1 ， ， k+l = 1 0 k 一2 , 0 i= 0 ， 1 ， 0 ， 0 尼 一1 。 由图 1可得 ： 6l ，j 一 1 ， 0 P = bl 。 。0 61，j ， 0 Pbl ，0 。 0 1 m 一1 ( 8 ) 61 ， 一1 ， 0 P = ( 1一P) b 1 ， 0 6 l ， ， 0 o 0 ( 9 ) 鼽 = ib l一,o ,o ( 10 ) 对于任意 0 ， 一1 ， ， 一 是 D1 一 f ( 卜 ) b 1

18、 0 =0 1 P r 6 _ 1 o 0 优 ( 1 1 ) 【 P c ( b l, m- 1 o+ b l ,m , o) = m 将公式( 8 1 O ) 代人( 1 1 ) ， 可以推出： = b , ,o , o J 。 。 ( 1 2 ) 所 有 的b ， 都 可 以 用 P 表 示 ， 而 且 1 卅 一1 b =l o 因此， 可以 求出所有的b ， 都可 i 0 j =O l=0 1 _ 一1 以用 b l ,o, o和P 表 示， 而 且b ， = l o 因 此 可 以求 出 、 ， l、 奄 O = 0 l L 一 优 + J 肌 ， 一 - 1 5 4 计算机技术与

19、发展 第 t 9卷 r = b 1 ， ， o = 2 ( 1一 e a a ) ( 1 2 p ) ( 1一 P ) E 2 ( 1 2 ) ( 1 一P ) +( 1 一e ) ( ( 1 2 p ) ( w0 +1 ) = = 1 1 ， 。 尸 ， r 一 ( 一r ) ” f = DI FS+ RTS + S I F S+ CTS+ SI FS+ H +E +S I F S+A C K ( 1 8 ) 【 = DI PS+ RTS 。 = ，z + 誓 + L 二 _ ! ( 1 9 ) 一 1 ， f 数据帧包括帧头和有效载荷， H 表示帧头的长 度 ， E表示平均有效栽荷的长度。

20、 当时归一化的系统吞吐量为： S= =仝时堕 捡查 夔蕉 垩塑盟间 时隙的平均长度 P t E P + P ( 1一P ) 十( 1一P ， ) ( 2 0 ) 2 仿真模拟分析 2 1 仿真环境 在 O p n e t 仿真实验中， 最大通信范围设为 1 0 0米 近似为圆形 区域 ， 网络中不存在 隐藏节点 ， 且所有节点 通过 I E E E 8 0 2 1 1 D C F协议共享唯一信道。包括 1 0 个无 线节点 的一个 网络拓扑 ， C l i e n t 1 C l i e n t 5和 S e r 、 ， e r l S e r v e r 5 均为无线节点。 对包含 1 0

21、、 2 0 、 3 0 、 4 0 、 5 0 、 6 0 个节点的网络拓扑进 行多组实验 ， 每个 网络拓扑中 ， 定义一半节点为客户端 ( C l i e n t ) ， 一半节点为服务器( S e r v e r ) ， 定义每一个服务 器对应一个客户端进行 F T P业务传输【 ， 引 。不同节点 数的 网 络 拓 扑 实 验 中， 分 别 基 于 基 本 访 问 模 式 和 R T S C T S 访问模式， 改变系统参数( 如初始竞争窗口 大小、 数据包大小等) 的设置， 统计介质访问延迟与这 些参数 的关系。 2 2 仿真参数 在分析模型和仿真实验中， 采用了与文献 4 ， 6

22、相 同的直接序列扩频( D S s S ) 的参数， 见表 1 。除了特别 说明， 文中的仿真实验中的数据包大小都设定为 1 k字 节( 即8 1 9 2比特) ， 仿真时间为 1 2 0 秒。 表 1 MA C层和采 用 D S S S的物理层参数 数据包8 1 9 2 b i t s MA C层包头 2 2 4 b i t s 物理层包头 1 9 2 b i t s A C K l 1 2 b i t s+ 物理层包头 R TS 1 6 0 b i t s+ 物理层包头 1 1 2 b its +物理层包头 信道速率 1 1 Mb i t s 传播延迟 时隙( s lo t ) 时间 d

23、S I Fs DI F S 2 3性能比较 由图 2 可知 3 M分组发送概率与 3 M 分组成功发 送概率分析， 当各站点的平均分组到达率分别为 8 、 2 4 、 1 2 8 p a e k e t s ， 站点数 目从 2 0增加到 6 0 个。系统饱 和前， 随着分组到达率站点数的上升， 网络负载增大。 因为碰撞概率q l l , ， 发送概率与成功发送概率几乎相 等， 所以数据侦的发送概率与系统吞吐量随之增大， 曲 线非常吻合。 图 3分别显示 了基本访 问模 式( 左半 图) 和 R T S C T S 访问模式( 右半图) 下 MA C层吞吐率的仿真结 果。从这两个图中都可以看出

24、： ( 1 ) 在基本访问模式和 R T S C T S访问模式下， 三 维 Ma r k o v 模型的 I E E E 8 0 2 1 1 D C F机制的吞吐率分 别平 均提高 了 2 4 7 和 8 7 ； ( 2 ) 随着 网络 中活 动节点数 的变化 ， 三维 Ma r k o v 第 7期 董明忠： I E E G q 0 2 1 I I X T F饥制的三维 Ma r k o v模型分析与仿真 1 5 5 模型的 I E E k k S 0 2 1 1 D C F机制 的吞吐率性能表现得更 加稳定 ， 而标 准的 I E E G q 0 2 1 1 I ) ( 机制 的吞吐率

25、随 着网络中竞争 节点 数 的增 加 而 降低 一 7 。对 于 三维 Ma r k o v 模型， 各站点的分组到达率越大， 系统吞吐量 增加越快。系统饱和后 ， 网络负载继续增大， 因碰撞造 成的数据传输次数增 多 ， 碰撞 概率增大 。虽然数据 侦 的发送概率和成功发送概 率增 加 ， 但系统吞吐 量保持 不变。 1 4 O l 2 0 t 0 0 爵8 o 4 6 。 O 2 o O 台 A 至 、， 胖 吉I 临 2 O 2 S 3 O 3 5 Nu mb e r o f No d e s I 4 0 童 1 2 0 姆1 0 0 薰 毽2 0 0 2 0 2 5 3 o 3 5 节

26、点数( 图 2 3 M 分组发送概率与成功发送概率 l 21 4 l 6 1 8 l 1 O 1 1 2l 仿真时间 ( 秒) 复 ： 。 。 Ma r k o v 模型 分 析 的 结 果 ( 实 线 ) 与仿 真 实 验 ( 符 号 “ ” ) 非常稳合 ， 而用文献 8 的 Ma r k o v 模型分析的结 果都明显偏大。究其原因， 主要是由于文献 9 中的模 型没有考虑退避过程中的冻结状态， 分析出来的冲突 概率就会比实际情况偏大， 冲突时间变长， 导致计算出 的介质访问延迟比实际值偏大。 3 结束语 通过三维 Ma r k o v 模型分析了 I E E E B 0 2 1 l D

27、 C F机 制的非饱和性能， 通过分组发送率、 吞吐率、 介质延迟 的仿真实验对模型进行了验证， 结果显示模型求解的 分析值与仿真实验结果拟合的很好， 并且仿真表 明 3 M模型在饱和与非饱和情况下， 其优化性能与稳定 性都 比原 I E E E B 0 2 1 1 D C F机制 有所 改善。后续 研究 是进一步计算活动节点与最优化竞争窗口、 负载、 分组 的长 度对介 质延 迟、 吞 吐率 的影 响， 并 通过 三维 Ma r K o v 模型进行分析仿真。 参考文献 ： 1 B i a n c h i GP e r f o r ma n c e A n a ly s i s o f t

28、h e I E E E 8 0 2 1 1 D i s t r i b u t e d C o o r d i n a t i o n F u n c t io n J I E E E J o u r n a l O n S e l e c t e d A r e a s i n C o mmu n i c a t io n s ， 2 0 0 0， 1 8 ( 3 ) ： 5 3 5 5 4 7 2 何昆鹏， 李腊元 A d H o c网络中按需路由协议的仿真与性 能分析 J 计算机技术与发展 ， 2 0 0 8 ， 1 8 ( 3 ) ： 8 1 8 4 3 李云 I E E E 8 0

29、2 1 1 D C F的 2种媒体访问控制 J 雠3M D C FF l 2 1 4l 6l 8 l l 0l l 2 1 仿真时间 ( 秒 ) 图 3 两种模式下 MA C层的吞吐率 l 0 2 0 3 D 4 D 5 D 6 0 1 0 2 0 3 0 4 0 节点数目 节点数目 图 4 两种模式下的介质访 问延迟 分析与仿 真结果的比较 图 4 分别显示了基本访问模式( 左半图) 和 R T S C T S 访问模式( 右半图) 下， 数值计算与实验仿真的情 况 。可以看 出来 ， 在两种模式下 ， 用 文 中提 出 的 三 维 模式问的公平性分析 J 重庆邮电学院学报： 自 然科学版，

30、 2 0 0 5 ( 2 ) ： 3 6 4 0 4 王春江， 耿方萍 ， 刘元安 ， 等 一种应用于 A d H o e 无线 局域 网的随机接 人协 议 J 电子学报 ， 2 0 0 5， 3 3： 212 5 5 Me s t d a g h D J G ， S p r a y * P M P A m e t h o d t O r e - d u c e t h e p r o b a b i l i t y o f c l i p p i n g i n DMT b a s e d T r a n s c e i v e r s J J I E E E T r a m o n C o

31、 m m， 1 9 9 6 ， 4 4 ( 1 O ) ： 1 2 3 41 2 3 8 6 D a v i s J A，J e d w a b j P e a kt O 一1T l e a n p o w e r c o n t r o l i n 0R) Go l a y c o mp l e me nt a r y s e q u e n c e s a n dR e e d Mu l l e r c o d e s J I E E ET r a m O i l I r d o r ma t i o n Th e o r y ， 1 9 9 9 ， 4 5 ( 7 ) ： 2 3 9 72 4 1 7 5 0 6 0 7 贺前华 陆以勤， 韦 岗 一种新的H MM 训练方 法 J 电子学报， 2 0 0 0 ( 9 ) ： 3 1 3 6 8 刘彩霞， 邬江兴， 程东年 基于多维状态 Ma r k o v 模型的一种无线信道规划方法 J 通信与计算 机 ， 2 0 0 4 ( 1 ) ： 4 l 一4 5 9 陈羽中 I E E E 8 0 2 1 1 D C F退避机制分析和改进【 J 应用 科学学报， 2 0 0 6 ( 7 ) ： 1 2 1 4 H 驻