网络通信与交换理论

姓名：李登峰                        学号：12012002305

由于纯 ALOHA 算法浪费较多时间，因此，如何节约时间是对纯 ALOHA 算法最简单改进。 时隙 ALOHA(Slotted-ALOHA)算法是对纯 ALOHA 算法一种最简单的节约时间的改进算法， 这种算法是在纯 ALOHA 算法基础上把阅读器发送信号的时间划分成多个连续的离散时隙（slot） ，时隙长度由系统时钟控制。本算法系统需要满足：1）每个时隙的长度必须大于标签发送数据所需时间；2）系统各控制单元必须与时钟控制单元同步；3）标签必须在系统约定的时隙内向阅读器传输数据；4）同步时钟使阅读器可识别范围内标签时隙同步。与基本 ALOHA 算法相比， 时隙 ALOHA 算法中任何一个时隙内只存在一个标签成功识别或无标签响应或多个标签完全碰撞，没有基本 ALOHA 算法中的部分碰撞，如下图所示，所以返回数据发送碰撞的时间减少一半，这样提高了信道利用率，系统吞吐率提高一倍。

图1 时隙ALOHA的工作原理

图1为两个站的时隙ALOHA的工作原理示意图。图中的一些向上的垂直箭头代表帧的到达。时隙的长度是使得每个帧正好在一个时隙内发送完毕。从图1可看出，每一个帧在到达后，一般都要在缓存中等待一段时间(这时间小于T0)，然后才能发送出去。当在一个时隙内有两个或两个以上的帧到达时，则在下一个时隙将产生碰撞。碰撞后重传的策略与纯ALOHA的情况是相似的。

现在推导时隙ALOHA的吞吐量公式。吞吐量S与网络负载G的定义与纯ALOHA的相同。

    参阅图1，设一个帧在某个时隙开始之前到达。显然，此帧能够发送成功的条件是没有其他帧在同一时隙内到达。因此，吞吐量公式

                           （1-1）                                  

此公式为Roberts在1972 推导出来的。当G = 1时，最大吞吐量。图3画出了式(1-1)表示的曲线。为便于比较，纯ALOHA的吞吐量且也画在同一坐标中。可以看出，对于时隙ALOHA，不稳定区域位于的部分。

图 2  Aloha 系统中的吞吐特性曲线

%matlab原代码

G=0:0.1:5;

S1=G.*exp(-2*G);

S2=G.*exp(-G);  

plot(G,S1,'r--',G,S2,'b-'); 

xlabel('单位时间平均交换的数据包量G'); 

ylabel('吞吐量S');     

legend('纯Aloha','时隙Aloha');

grid on;

由泊松过程的定义：，                     (1-2)

从而可以知道在一个时隙中有一个数据包到达的概率为，对于每个节点而言，。仿真时，我们认为每个节点每个时隙最多只会到达一个数据包，故仿真时可以以一个时隙为步长，每个节点每个时隙到达一个数据包的概率就为，由此，对每个节点生成一组随机数，当此随机数小于等于，则表示有一个数据包到达，把此随机数用1代替，反之则没有数据包到达，把此随机数用0代替，这样可以得到每个节点在某个时刻是否有数据包到达的矩阵，然后把每组矩阵相加，得到某一时刻总的到达的数据包，当某一时刻为1时，总共只有一个数据包到达，则可以成功传送，对于每个给定的，取多个时隙作多次重复试验，则可以得到这多次重复试验中成功传送的次数，用成功传送的次数除以总的重复试验次数，就是成功传送的概率。对不同值，用上述方法，就可以得到不同值对应的成功传送的概率。此外，对于给定的，对于时隙长度1有。

下面是m=3000,取5000个时隙点，在[0,3]间对应的成功率、碰撞率和空闲率如图4：

图3

%matlab原代码

clc;clear

close all

m=2000;

t=1300;

z=[];

Su=[];

Sb=[];

Si=[];

for G=0:0.1:1

    p=G/m;  

    x=rand(m,t);

for i=1:m

for j=1:t

if x(i,j)<=p

                x(i,j)=1;

else

                x(i,j)=0;

end

end

end

    y=(sum(x));

    z=[z,sum(y==1)/t];

    Su=[Su,G*exp(-G)];

    Sb=[Sb,1-exp(-G)-G*exp(-G)];

    Si=[Si,exp(-G)]

end

G=0:0.1:1;

plot(G,z,'r*')

hold on

plot(G,Su,'-',G,Sb,'go',G,Si,'--')

xlabel('G')

ylabel('到达率（bps）')

legend('成功传输的次数','成功率','碰撞率','空闲率')

grid on

二、非隔离型二叉树冲突分解算法MATLAB实现L=4

%非隔离型二叉树形冲突分解算法 

% m=2

clc,clear

syms n

p=0.5;

p20=2*(p^2)*(p^0);

p11=2*(p^1)*(p^1);

f=n*(p11)*(p20)^(n-1);

N2=symsum(f,n,1,inf)

L2=2*N2

% m=3

p30=2*(p^3)*(p^0);

p21=2*3*(p^2)*(p^1);

f1=n*(p21)*(p30)^(n-1);

f2=N2*(p21)*(p30)^(n-1);

N3=symsum(f1,n,1,inf)+symsum(f2,n,1,inf)

L3=2*N3

%m=4

p31=2*4*(p^3)*(p^1);

p40=1-p31;

f1=n*(p31)*(p40)^(n-1);

f2=N3*(p31)*(p40)^(n-1);

N4=symsum(f1,n,1,inf)+symsum(f2,n,1,inf)

L4=2*N4

运行得：N2 =2        L2 =4

N3 =10/3     L3 =20/3

N4 =16/3     L4 =32/3

即时，计算结果如下：

N4 =16/35.33    L4 =32/310.66