dsfds' blog

学海无涯，回头是岸

0%

信道共享技术简述与ALOHA的仿真

发表于 更新于 分类于 Valine：

MAC（Media Access Control）协议，即介质访问控制协议。MAC层需要实现数据帧的封装卸装、帧寻址和识别、帧的接受和发送、链路的管理和帧的差错控制等。屏蔽了不同物理链路的种类差异性。其核心是对有限物理资源的高效利用。在Ad Hoc网络中，由于其无中心和使用无线信道等特点，新带来的问题有：选择什么样的信道共享方式，如何处理终端暴露问题，如何隐藏终端，以及如何处理节点移动带来的影响。因而对MAC协议的要求更高。本文将探讨简单的信道共享技术，并对动态接入协议ALOHA进行分析和
MATLAB仿真。

信道共享技术分类

信道共享技术又称为多点接入技术，原理是通过一个专用信道将所有的用户连接起来。按照多个用户与一个主机连接的访问方法来划分，信道共享技术可以分为通过集中器或复用器相连和直接相连，前者即信道复用，后者又可分为受控接入和随机接入。

信道复用

这是一种应用的比较成熟的技术，集中器或复用器按顺序不断扫描各个端口，或采用中断技术来接受用户信息或转发。如FDM，TDM，CDM，WDM和STDM。
考虑一个实际例子：两个用户A和B，都需要需要发送信息；如果采用FDM方式，则分别为A和B分配一条不同频率的信道，允许二者一起发送而不产生冲突；如果采用TDM方式，则A和B的数据帧交给集中器，集中器把二者的帧放在不同的时隙发送然后发送，也可以避免冲突。这可以通过集中器扫描，也可以通过用户发送请求产生中断来执行。
其实这就是一种静态的信道分配，按频率、时间或码字对信道进行划分。显然，这会造成资源的浪费。

受控接入

受控接入方式的网络拓扑是环型结构，分为集中式控制和分散式控制。集中式控制使用轮询方法，主机按顺序逐个询问各站是否有数据需要发送。分散式控制即使用令牌，在环路中有一个特殊的帧——『令牌』，沿着环路传递，只有获得了令牌的站才有权发送信息。

随机接入

随机接入方式的网络拓扑是总线型结构，所有的站点可随时发送数据，争用信道，容易产生冲突，经典的协议有ALOHA，CSMA和CSMA/CD。

信道的静态和动态分配

信道的静态分配即将信道资源N等分，这个资源包括时隙（slot）、频谱（frequency）和码字（code），适用于用户数量少、数据量大的情况。这种信道的分配方式在某系情况下是不合理，它不能满足用户对资源占用的不同需求，效率低，不合适多站点，不适于突发性数据。

信道的动态分配使用多路访问协议，动态分配信道资源提高信道利用率。可以这么理解：不对信道资源进行划分，用户产生了需求就进行处理，处理时占用全部的信道资源。这么做不可避免的会产生信道争用和冲突问题，可以牺牲一点自由，使用受控接入方式可以隐藏争用问题和解决冲突问题。或者可以直面信道争用和冲突，使用随机接入方式，其中一个重要的协议就是ALOHA。

从一个更高的角度上来看，信道复用技术是一种信道的静态分配技术，受控接入和随机接入是一种信道的动态分配技术。

ALOHA

前面讲到，ALOHA协议是一种信道的动态分配协议，它实现了信道共享方式中的一种随机接入技术。在这种动态分配的方式下，信道有三种状态，传输，空闲和竞争，所有的站点都通过同一信道发送或接受帧，某一特定时刻只允许一个站点使用信道。

以一个数据帧A的发送为例，考虑其如何才能成功发送。发送时机有两种选择，连续时间或时间片，前者允许在任意时刻发送，后者将时间用时钟分离为片段，帧只允许在每一个片段开始瞬间发生。若是以连续时间发送，帧发送时，若信道是空闲状态，则成功开始发送帧，此时信道为传输状态，假设在帧发送时间内又有数据帧B的发送请求产生，则信道进入竞争状态，产生了冲突，帧A发送失败，帧B也发送失败，都需要重传，二者分别随机等待一段时间，然后进行发送，直到发送成功。


aloha_principle_illustration
纯ALOHA帧传输示意图

我们把以连续时间发送的称为纯ALOHA（pure ALOHA），按时间片发送到称为时隙ALOHA（slotted ALOHA），下面对它们的信道利用率进行分析。

pure ALOHA 信道利用率分析

首先考虑pure ALOHA中一帧发送成功的条件，假设帧长固定，发送所需时间为T，则不难推知发送成功的条件为该帧发送前后各有一段T时间内没有其他帧发送，如下图所示。


pure_aloha_success
纯ALOHA的帧发送成功条件

对其信道利用率分析我们先要确定一些条件：

  • 假设：帧长固定，无限用户，按泊松分布产生新的数据帧。
  • 网络负载为G，表示在T内总共发送的平均帧数，包括发送成功的帧和因碰撞未发送成功的帧。
  • 吞吐率为S，表示在帧的发送时间T内成功发送的平均帧数。

简单分析可知，0<=S<=1，S=0表示在信道上无成功发送的数据；S=1表示数据帧一个接一个发送，这是不可能的。G只有在不发送碰撞时才和S相等，且可以远大于1。

我们研究信道利用率，就是要考虑在什么的样的网络负载下，能够取得最大的吞吐率，并且要知道这个最大的吞吐率。

对这个问题进行理论分析并不困难，稳定情况下，S=G*P[发送成功]，求出一个数据帧发送成功概率P即可，由前面的分析可知，当前帧要想发送成功，以为着当前时刻的前后T时间内，共2T时间内，没有其他数据帧的发送请求产生，按照数据帧的产生数或者说数据帧请求产生数在T时间内服从参数为G的泊松分布，不难得出P[发送成功]=((2G)^0/0!)*e^(-2G)，则吞吐率S=G*P[发送成功]=G*e^(-2G)，求极值可知，当G=0.5时，S取最大值0.184，非常小。

对这个过程进行MATLAB仿真并不难，具体思路如下：产生一系列值的G，对每一个帧，产生若干个服从参数为G的泊松分布随机数，若连续的前后两个随机数和为0，则表示发送成功，统计发送成功的数占所有随机数的比即为该负载G下发送成功的概率，在和G相乘求得此时的吞吐率S，对每一个G都这么求即可得出一系列的(G,S)，再使用plot作出图像，如下所示：


pure_aloha
纯ALOHA的信道吞吐率与网络负载的关系

slotted ALOHA 信道利用率分析

时隙ALOHA协议下，将信道时间划分为离散的时间隙，隙长为一个帧所需的发送时间，每个站点只能在时隙开始时才允许发。

分析信道利用率时，条件和纯ALOHA相同。重点也是在考虑发送成功的概率，在时隙ALOHA协议下，当前帧发送成功的条件为：当前发送时隙前的一个时隙T内没有新的数据帧发送请求产生。事实上，由于只允许在时隙开始时发送请求，站点发送的数据帧都是积攒下来的。可以求出P[发送成功]=(G^0/0!)*e^(-G)，S=G*e^(-G)，当G=1时，S取最大值0.368，是纯ALOHA的2倍，但还是不够高。
仿真思路同纯ALOHA，最后作出的S-G图像如下所示：


slotted_aloha
时隙ALOHA的信道吞吐率与网络负载的关系

附MATLAB仿真代码：

aloha_.mview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
clear all;clc;
% ALOHA 仿真
% 网络负载G
% 成功发送条件，请求为0
T = 100000;   % 仿真时间 1000个帧长
load_scale = 0.1;
G = 0:load_scale:5; % 网络负载
requests = zeros(T+1, size(G,2)); % 请求次数
pure_ALOHA_sucess = zeros(1,size(G,2)); % pure ALOHA成功次数
slotted_ALOHA_sucess = zeros(1,size(G,2)); % slotted ALOHA
% 产生请求
for g = 1:size(G,2)
    requests(:,g) = random('Poisson',G(g),T+1,1);
end
% pure ALOHA
for g = 1:size(G,2)
    for index = 1:T
       if requests(index,g) + requests(index+1,g) == 0
           pure_ALOHA_sucess(g) = pure_ALOHA_sucess(g) + 1;
       end
       if requests(index,g) == 0
           slotted_ALOHA_sucess(g) = slotted_ALOHA_sucess(g) + 1;
       end
    end
end
%% calculate
% pure ALOHA
probl_pure_ALOHA = pure_ALOHA_sucess / T; % 成功概率
S_pure_ALOHA = G.*probl_pure_ALOHA;       % 吞吐率
% slotted ALOHA
probl_slotted_ALOHA = slotted_ALOHA_sucess / T;
S_slotted_ALOHA = G.*probl_slotted_ALOHA;
%% plot
% pure
figure(1)
yyaxis left
plot(G,probl_pure_ALOHA)
ylabel('Probablity of Sucess')
yyaxis right
plot(G,S_pure_ALOHA)
title('Average Throughput of Pure ALOHA')
xlabel('G')
ylabel('Average Throughput')
grid on
% slotted
figure(2)
yyaxis left
plot(G,probl_slotted_ALOHA)
ylabel('Probablity of Sucess')
yyaxis right
plot(G,S_slotted_ALOHA)
title('Average Throughput of Slotted ALOHA')
xlabel('G')
ylabel('Average Throughput')
grid on