第 28 卷第 1 期
2010 年 1 月
吉林大学学报(信息科学版)
Joumal of Jilin University (Infonnation Science Edition)
Vol. 28
文章编号: 1671-5896(2010 )0I -000l3-07
基于随机多址协议的系统吞吐量分析
余明辉赵东风2
(1.泊洲湾职业技术学院电子工程系，福建青田 351254; 2. 云南大学信息学院，昆明 650091 )
摘要:为解决当多个用户通过一个公共信道与其他用户进行通信时必须采用多址技术的问题。在详细阐述了
时隙 ALOHA 系统和连续时间 ALOHA 系统以及非坚持 CSMA (Carrier Sense Multiple Access) 控制协议的分析
的同时，分别得出了 3 种系统的平均成功队长和系统吞吐量的数学表达式，并通过仿真实验验证了理论分析
的正确性。
关键词:随机多址;信道;循环体;平均周期;吞吐量
中图分类号 文献标识码:A
Analysis Throughput ßased on Stochastical Multi-Addresses of System
SHE Ming-hui 1 , ZHAO Dong-feng2
(1. Department fo Electronic Engineering , Meizhouwan Institute of Technology , Putian 351254 , China;
2. Institute of Information , Yunnan University , Kunming 650091 , China)
Abstract: To address when multiple users through a common channel to communicate with other users must use
multiple access technologies. Slotted ALOHA in the elaboration of the ALOHA system and the continuous-time
systems as well as non-persistent CSMA (Carrier Sense Multiple Access) control protocol , while the analysis
were obtained three kinds of systems , the average successful captain and system throughput mathematical expres-
sion , and through simulation experiments verify the theoretical analysis is correct.
Key words: stochastical multi -addresses; signal channel; loop body; average period; throughput
引 斗=口
多址协议( MAP : Multiple Access Protocol) 是在一个网络中，解决多个用户如何高效共享一个物理
链路的技术[lm7]O 典型的共享链路网络有:卫星和蜂窝移动通信系统、局域网和分组无线电网等。在网
络中，当多个用户同时发送时，将发生多个用户的帧在物理信道上相互重叠(即碰撞) ，使接收端无法
正确接收[8J 。当多个用户竞争信道时，就会出现相互碰撞和信道空闲的现象，为了尽量避免用户之间
碰撞，并使信道利用率最高，就需要一个有效的协调机制(或服务准则)一一随机多址协议[9 -17J 。
1 时隙 ALOHA 系统
在时隙 ALOHA 系统( S-ALOHA) 中，所有节点同步，各节点只能在时隙开始点进行传输，时隙宽
度等于一个分组的传输时间(见图1)。
当一分组到达某时隙后，它将在下-时隙开始传输，并期望不会与其他节点发生碰撞。如果在某时
隙内，仅有一个分组到达(包括新到达的分组和重传分组的到达) ，则该分组将传输成功。如果在某时
隙内到达两个或两个以上的分组，则将会发生碰撞。碰撞的分组将在以后的时隙中重传。如果碰撞后，
收稿日期 :
基金项目:国家自然科学基金资助项目 (60362001;69862001; F04241004).
作者简介:余明辉(1965一 )，男，福建甫田人，酒洲湾职业技术学院副教授，硕士，主要从事随机多址通信、网络通信工程研究，( Tel)
86-13706097791 (E-mail)smh7791@;赵东风(1957- )，男，武汉人，云南大学教授，博士生导师，主要从事随机多
址、轮询多址和网络通信工程研究， (Tel) 86-13698761411 (E-mail) zhaodfOO88@ 126. ∞m。
第 28 卷吉林大学学报(信息科学版)14
..
立即在下一个时隙重传，将导致再次碰撞。
碰撞重传 重传
巳凸凸<'5f2?~ ~~
飞h每吨=r~ 一4卢卢..
l 时隙占25
T tt
分组到达 分组到达
图 1 时隙 ALOHA 系统
Fig. 1 The ALOHA system
系统模型
时隙 ALOHA 为了提高随机接人系统的吞吐量，使各站点时间同步，并将时间划分为多段等长的时
隙丸，每帧只能在每个时隙开始时才能发送[3] 。时隙的长度是使每祯正好在一个时隙内发送完毕。每
帧到达后，一般都要在缓冲区中等待一段时间(小于 To ) 才能发送出去。当在一个时隙内有两个或两
个以上的帧到达时，将在下一个时隙产生冲突。
假定成功用 U表示，空闲用 I表示，碰撞用 B 表示。 ALOHA 系统以时隙方式工作(见图 2) 。
1. 1
-:r
Ui + 4
Uî+ì IJ+2 Ur+1. 1; 吁 一-ι一一 Bk+1
m功明户一人一-，~ ，..--^-一-..~伽以牛啤瞄唰咀
t'
Ui 1, U1 +1 B~J;+l
Eb少%。如置 .于/'l切饵'悦目。配泪。.
i 些功空闲 碰撞
图 2 时隙方式 ALOHA 系统
Time slot the way ALOHA system
图 3 是图 2 用饵 ， UI) 划分的时隙方式 ALOHA 系统图。
-
『飞、 Bk +l
-'lff///.I.理'l/////刃，。自即哥啤酒
UI' +1
卢-^-
~ D盟
U1,
/一甲…一…"，'"，一一-一飞 B ，.--
彰男男男' 如切7/..1部棚响
i• t'
图 3 (B ， UI) 划分的时隙方式 ALOHA 系统
Fig. 3 Time slot (B , UI) the way ALOHA system
系统分析
在 S-ALOHA 系统中，信息分组的到达率为 G ， 时隙长度为 T (也可为单位时间)。
U 的概率为 P(I )P(1) ...p([) , BI 的概率为[ 1 一 P(1 )][1 - p([)J"'[1 - p([)J 。所以在一个循环体内，
( U ， BI) 概率分布
1. 2
P(i,j) = [p( l)]' [1 - P(1) JJ
其中 i=l ， 2 , 3 ,… ;j=l , 2 , 3 , ...。
因为
p" , 1 - P (1) 一一一~ _1
1 - p ,,, P (1) L ([) L LP(i ,i)
所以
P(i ,i) = [P([)]'[1 甲 P(1) Ji = (Ge- C )i (1 - Ge-C ) i
在一个循环体里，成功的平均数量 1一川Nu = L L iφ (iJ)
第 1 期 余明辉，等:基于随机多址协议的系统吞吐量分析 15
成功的平均长度
E( U) = 风 x 1 =一 1 一言
1 - Ge-"
----γ----r呵呵响啊?但--由r---
k
l 、、、、j
1'\.
---t-r-----r-咱---r---啕--t南飞了-t-句--伽宁白.由民 t----
同理 町
‘ \S-ALOHA'
‘\: ..寸
电\
、....1
平均长度
平均周期
吞吐量
NBI=z zjRM)=tE
E(BI) = NB1 X 1 =主E
lTe
--r----r----r----γ陪同 --γ自由-~、c---r---
、.....1
飞
--司'俨哼饵--俨----t----t----t-白白白t---相↑---町'
E( Tu ) = E( U) + E(BI)
S" = E旦L = Ge- G
u - E(T
u
)
当 G=1 时 ， S =Smax =e- 1 = ，时隙 ALOHA 协议
的最大吞吐量达到理想值的 % 。不稳定区域位于 G > 1
的部分。时隙 ALOHA 的吞吐量与到达率的关系曲线如图 4
所示。
2 连续时间 ALOHA 系统
2. 1 系统模型
O 2
G
3
图 4 时隙 ALOHA 的吞吐
量与到达率的关系曲线
Fig. 4 Time slot of pa时ition the relation of
arrival rate and the handling capacity of
ALOHA of time slot curve map
4
连续时间 ALOHA (P-ALOHA) 系统的基本思想:如果网络中的一个站点有数据要发送，则发送数
据包，而不管共享信道当前的状态，是一种完全随机的接入方法。如果源站点在规定时间内收到了日的
节点的确认，则认为通信成功，否则认为通信失败，游、站点重新发送这一帧数据[5] 。
ALOHA 系统以连续时间方式工作(见图 5) 。
E二二3 L书在j r「
1< t'<2
E二二3
图 5 连续时间的 ALOHA 系统
Fig. 5 The continuously time ALOHA system
图 6 是图 5 用饵 ， U1) 划分的连续时间的 ALOHA 系统图。
t* = T; +1
T;为两个信息分组到达的时间间隔
图 6 (B ， UI) 划分的连续时间 ALOHA 系统
Fig. 6 Continuous time (B , U1) the continuous time ALOHA system
系统分析
在 P-ALOHA 系统中的概率分布:
1) 两个相邻的信息分组发生碰撞的概率
P=iIf(仙= 1 - e-G
2) 两个相邻的信息、分组不发生碰撞的概率
q = r只忖 =J
"
16 吉林大学学报(信息科学版) 第 28 卷
P(nl = 监半兰 n = 0 ,1 ,2 ,
、 n'
f( t) = Ge -Gt , t ~ 0
对于 i + 1 个相邻的信息分组发生碰撞 P1P2 " ，Pi = P'(P1 = P2 = …= PJ;
对于j + 1 个相邻的信息分组不发生碰撞 Q1Q2"'qj = rj(Ql = Q2 = …= Qj) 0
3) 连续 i 个(r < 1) 和连续j 个(r > 1) 的概率分布
P(i ,j) = P'rj , i = 1,2 ,… ; j = 1,2 ,'
均值 E(i) = eG ; E(j)=Jτ j* (t) = 乒!L
1 - e JJ( t) dt t E [O , IJ
I if( t) dt
E( r) = 乓「二一=云丁·
IJ( t) dt tT 1 - e
图 7 为连续时间的随机多址系统图。
I if( t) dt
E( 扩) =乓r一←=云+ 1
l 只 t) dt
J
E(r*)
Eω
图 7 连续时间的随机多址系统图
Fig. 7 Continuous-time random multiple access system diagram
图 7 中 E( i) 为平均次数、平均个数为非完整段(r);E(r) 为平均长度 ; ] 为完整段( r' ) ;非完整段
的总长度为 E(rl r < I)E(i); 完整段的总长度为 E( r* )E(j) 0 故成功的平均个数为[E(j) - 1 J ;即可推
导出:成功的平均长度[E(j) -1] x10 总的非完整段的长度 E(rl r < l) E(i); 即可推导出:碰撞的总的
平均长度 E(rl r < I)E(i) + 1 。一个完整段中空闲的平均长度[E(r*lr* >1)-IJ; 即可推导出总的
空闲的平均长度 E(j)[E(r*1 旷 >1)-IJ; 吞吐量
Su = [E (j) -1J x l/ [E (j) -IJ xl +E(rl r < 1)E(i) +1 +E(j )[E(r* I r* > 1) -1] =
(1 _1 p -G - 1) x 1 1 - e -G ~ J 户 = Ge -2G
(-LEli × l+eEll-iL)+1+」一(~+1-1
_ e -G ~ J 飞 G 1 - e -G J . ~ . 1 - e-G 飞 G
当 G= 时 ， S=- 1 = ， 是吞吐量的极
大值。
由图 8 可以看出，当 G > 时，吞吐量开始下
降，将引起更多的重传，因而使到达率 C 进一步增大，
恶性循环使吞吐量下降到零，整个系统不能正常工作。
因此在连续时间 ALOHA 系统中，到达率 G~定
不能大于 。一个理想随机接人系统的吞吐量 S 的极 图 8 连续时间 ALOHA 的吞吐量
限值是 1 ，而连续时间 ALOHA 的吞吐量的极大值只能 与到达率的关系曲线
达到理想值的 % 。控制的简单性是以牺牲信道容 Fig. 8 The relation of arrival rate and the handling
量为代价的。 capacity of continuous time ALOHA curve m叩
甲甲
一
-E"
一一-
l
寸
ll471IAll-
寸
----E
一--
ir--+llLI--r
"--叫一一-一-E明甲
l
寸l141iAi1-
「
牛
"zip
--MAE
』
iTll
千leill-B
『
"-JU
』『
一一，寸』1「
ll
←
iEpilh
「
-一一、一-"-h
、
d
H
一-、
i
寸
i1
斗
ll
，吨，
ll
寸
』一出--h-P
!Til+1·
申LiltT
一一/-一半叶-
3 4
第 1 期 余明辉，等:基于随机多址协议的系统吞吐量分析
3 非坚持 CSMA 控制协议
3. 1 系统模型
17
随着网络的发展，网络上的数据流量不断增加，传输数据时，共享信道上产生冲突的可能性就变得
很大，在这种情况下， ALOHA 协议不再能有效地工作。因此提出一种新的随机接人方法，即载波侦昕
多址接人( CSMA: Carrier Sense Multiple Access) 。其基本思想是，如果网络中…个节点有数据要发送，
则首先监听信道，如果当前信道空闲，则发送数据包;如果信道忙，则等信道空闲后再发送数据包。如
果源节点在规定时间内收到了目的节点的响应，则认为通信成功;否则认为通信失败，源节点等待一个
随机的时间后重新发送这一帧数据[叫。
根据赵东风[7] 提出平均周期划分方法对系统进行 (I， BU) 的划分，发送信息分组的情况如图 9 所
刁亏。
I
τ a
图 9 平均周期的 (I， BU) 划分非坚持 CSMA 系统
Average period (I, BU) divide the relation that not insists CSMA system
系统分析
CSMA 协议对 ALOHA 协议进行了改进，在发送数据前首先检测信道，从而减小了冲突发生的可能
性。如果收不到目的节点的 ACK，则等待随机时间后再重发数据帧[町，从而减小了再次冲突的可能性。
载波侦听(检测)型多址( CSMA) 在发送信息分组前对当前信道的状态进行检测。检测信道空闲时，
发送信息分组占用信道。检测信道忙时，不发送信息分组。这时进行以下两方面工作:第一，检测持
续，直到信道空闲;第二，随机后退一段时间，然后再次检测。
平均周期方法
s = _U
B + 1
其中 S 为吞吐量 ， U = E( U) , B = E(B) , 1 = E(I) 。
根据 p(n) = 坠平士，其中 n=O ， 1 ， 2 ， 3 ，知知α-y州的概率为J
、 n!
从图 9 知，随机变量 y 的概率分布可表示为
F<;) = PrjY~ yl = Pj 在(α- y) 中没有信息分组到达 1 = expj - G( α- y) 1 , 0 运 y 运 α
根据
fyf/ dy = E(y) = Y
得
E(y) = Y = α - lIG(1 - eG-aG )
所以平均循环周期内忙周期的平均长度
E(B) = E(y) + 1 +α=α- 专(1 _e-aG ) +1 +α= 1 + 2α 斗圳→-aG) 运 1 + 2α
B = E(B) = 1 + 2α - lIG(1 - e-aG ); E (I) = lIG
1 = E(I) = lIG, E(U) = 1 x e-aG
U = E( U) = 1 x e -aG
s=_U__ lx ♂G GfG 一
- ----
-B +I 一 1 + 2α - lIG(1 - e-aG ) + lIG - G(1 + 2α) + e -aG 故
18 吉林大学学报(信息科学版)
当 α趋于O 时 ， S = Smax = G/1 + G = 1 ，吞吐量达到极大值。
由图 10 可以看出，非坚持 CSMA 协议的最大吞吐量大大提高，
系统的吞吐量 S 的极限值是 1 ，达到理想值 100% 。
4 计算机仿真实验与结果分析
基于上述分析，在 仿真环境下，对随机多址协议 。1
下的系统进行仿真，图 11 给出了时隙 ALOHA 与连续时间 ALO 。
HA 以及非坚持的 CSMA 的吞吐量的比较关系曲线图。由实验结
第 28 卷
下一I一一一下一一厂一「
-I""----r-----r句句--r----r----r----r----
1飞
一-1 \"---t一一-↑一一←-一←一叶'一-1"一-
I \
1 \
\ I
\.1
----I""--~r-----r-吨---俨 ----r----r--由命r---
't
i\臼MAl
1 、、
--响噜4卡----t----.，..鬼--幅"卡----卡----r----I"---
、~
3 4
果可以得到以下结论。
1)时隙 ALOHA 协议比连续时间 ALOHA 协议吞吐量提高
图 10 非坚持 CSMA 吞吐量与
到达率的关系曲线图
了一倍。不稳定区域也由 G >0. 5 变为 G > 10 S-ALOHA 系统和 Fig. 10 Not insÍst CSMA handling
P-ALOHA 系统的共同特点是有信息分组要传送就占用信道发 capacity and a时val rate curve map
送。要使吞吐量提高，则要减小信息分组发生碰撞所占用的信
道资源(时间)。
2) 非坚持 CSMA 系统比时隙 ALOHA 系统与连续时间纯 ALOHA 系统吞吐量提高了很多，不稳定区
域也随之降低了很多。
到达率 G
图 11 时隙 ALOHA 与连续时间 ALOHA 以及非坚持 CSMA 的吞吐量
Fig. 11 Continuous time ALOHA and ALOHA of time slot as well as not insist the handling capacity of CSMA
5 结语
多址通信技术在现代通信中起着重要作用。在卫星通信、计算机通信、移动通信等网络中，当多个
用户通过一个公共信道与其他用户进行通信时，必须采用多址技术。笔者对时隙 ALOHA 系统和连续时
间 ALOHA 系统以及非坚持 CSMA 系统的主要方面进行了分析，并对随机多址系统平均长度、平均周
期、吞吐量等分析方法进行了较全面的论述，得出了完整的数学表达式。计算机通信仿真实验结果表明
了理论分析和仿真实验的一致性与合理性。
参考文献:
[ 1 ]LEONARD K, FUUAD A TOBAGZ. Packet Switching in Radio Channels: Part I-Carrier Sense Multiple-Access Moder and
Their Throughput-Delay Characteristics [J]. IEEE Trams Commun , 1975 , 23 (12): 14∞-1416.
第 1 期 余明辉，等:基于随机多址协议的系统吞吐量分析 19
[ 2 J ROYER E M. A Review of Current Routing Protocol for Ad Hoc Mobile Wireless Networks [J]. IEEE Personal Communica-
tions Magazine , 1999 , 6 (2): 46-55.
[ 3 J STEPHAN E , JEWITI J. TPPM Reporting MIB [1]. N etwork W orking Group Intemet Draft , 2003 (3): 17 -20.
[4 JSTEPHAN E: IPPM Metrics Registry [J J. Network Working Group Inter咀et Draft , 2∞'3(4):4549.
[5 JWILLISAM STALLINGS. 无线通信与网络 [MJ. 第 2 版.何军，译.北京:清华大学出版社， 2∞5.
WILLISAM STALLINGS. It is Wireless to Communicate with Network [M J. 2nd ed. Beijing: Tsinghua University Press ,
2005.
[6 JSAADAWI T N. 远程通信网络基础 [MJ. 黄岩，译.北京:电子工业出版社， 1996.
SAADAWI T N. Long-Range Communication Network is Basic [MJ. Beijing: Publishing House of Electronic Indust巧， 1996.
[ 7 J赵东风.一种新的时间连续型随机多址系统分析方法研究[JJ. 电子科学学刊， 1999 , 20 (1): 3741.
ZHAO Dong-feng. Study on a New Method for Continuous-Time Systems of Random Access Channel [J J. Joumal of Electron-
ics , 1999 , 20 (1): 37 -41.
[ 8 J 王承恕.通信网新技术 [MJ. 北京:人民邮电出版社， 2∞6.
W ANG Chen-su. Communicate to Net New Technology [M J. Beijing: Posts & Telecommunications Press , 2006.
[ 9 J 周炯磐.通信网理论基础 [MJ. 北京:人民邮电出版社， 1991.
ZHOU Jiong-pan. Communicate to Net Theoretical Foundation [M J. Beijing: Posts & Telecommunications Press , 1991.
[ lO J曾华条.现代网络通信技术 [MJ. 成都:西南交通大学出版社， 2006.
ZENG Hua-yan. Modem Network Communication Technology [M J. Chengdu: Southwest Traffic University Press , 2006.
[11 J沈连丰.信息与通信工程原理与实验 [MJ. 北京:科学出版社， 2∞7.
SHEN Lian-feng. Info口nation and Communication Project Principle and Experiment [M J. Beijing: Science Press , 2∞7.
[ 12J赵东风.时隙式随机争用多址系统分析方法研究[JJ. 通信学报， 1999 , 20 (8): 80-85.
ZHAO Dong-feng. Study on the Average Cycle Method for Slotted Multiple Access Communications [J J. Joumal on Communi-
cations , 1999 , 20 (8): 80-85.
[13 J刘彬彬，赵东风，丁洪伟.基于概率检测的时隙式多通道随机多址元线通信网络协议分析 [J J. 通信学报， 2∞6 ，
27 (12): 70-75.
LIU Bin-bin , ZHAO Dong-feng , DING Hong-wei. Analysis of Slotted P-Detection Multi-Channel and Random Multi-Access
Protocol for Wireless Communication Network [J]. Joumal on Communications , 2006 , 27 (12) : 70-75.
[14 JNICOPOLITIDIS P , PAPADIMITRIOU G 1, OBAIDAT M S , et al. Carrier-Sense-Assisted Adaptive Leaning MAC Protocols
for Distributed Wireless LANs [JJ. Intemational Joumal of Communication Systems , 2005 , 18 (7): 657 -669.
[15JHAN Y S , JING DENG , HAAS Z J.. Multi-Channel Medium Access Control Schemes wi由 ALOHA Reservation [J J. IEEE
Transactions on Wireless Communications , 2∞6 ， 5 (8): 214
