多信道跳频网络的协议序列性能研究∗
2018-08-01滕文
滕 文
(陕西国际商贸学院信息与工程学院 西安 712046)
1 引言
随着自组织网络、传感器网络和射频识别的发展,针对这些系统设计简单高效的多址接入算法要求对这些方法进行重新审视,尤其是传感器网络提出了挑战。除了拥有大量分布在动态变化的网络拓扑结构中的设备,传感器通常具有非常严格的尺寸和功耗要求。因此,应用简单的随机访问协议不需要频繁地对反馈信息的信道进行监测,并且可以避免复杂的处理过程,如后退算法或随机数生成,但是随机访问也有一些局限性。比如造成冲突的概率较高,因此用于重传的消耗较大,吞吐量不够高,时延也较大。虽然用多信道网络可以缓解用户间的竞争问题,但也不尽如人意。多信道共用可以提高信道利用率,进而提高网络的吞吐量,减少用户的时延。但是工作在多信道里的系统要比工作在单信道里的复杂得多。就移动台来讲,首先,它必须适应工作频率有多个的特点,而不是单一的,并且调谐是自动的;其次,要能判别信道的空闲状态,只有空闲信道才能占用,否则会发生冲突。在无反馈的信道中,冲突的发生就意味着信息传输的失败;最后,系统必须具有自动转换到任一空闲信道上的能力,使信道利用率尽可能高。在这种背景下,协议序列就被提出用以解决这些问题。协议序列多用于多包接收,多址技术以及多信道网络等无反馈的信道里,具体可以应用于新兴的通信系统中。
2 GRT协议序列
2.1 工作原理
协议序列常用于无反馈的冲突信道中,但是为了使系统吞吐量随时延补偿的波动最小,我们需要构造一种协议序列使其一对汉明互相关尽可能的接近于常量。在这个课题中主要应用到一种协议序列是基于中国余数定理(CRT)将一维序列映射到二维数组。将CRT序列应用于无反馈的冲突信道时,最差情况的下界将被导出。
被提出的CRT序列有两个特点:用户识别能力和帧同步能力。每个被成功接收的数据包的发送者可以仅仅通过识别信道活跃程度而被识别,不用考虑数据包内容。使用中国余数定理产生一组p行q列的矩阵,每一行中1的个数和位置都是指定好的,每一行对应一个用户,当所对应位置为1时,用户发送信息,对应位置为0时,用户保持静默,而且每一列只能有一个1的存在,说明在一个时隙中只有一个用户在发送信息才不会发生冲突。用CRT序列控制用户的状态可以避免冲突,减少时延,提升网络吞吐量。
对于随机访问协议,原理就是设置一个发送概率,在仿真过程中产生一个随机数,只要这个随机数小于这个概率,用户就发送信息,要是随机数大于这个概率就保持静默,因为每个用户是独立的所以可能出现有多于一个用户同时发送信息的可能性,因此产生冲突的可能性相对较大,一旦冲突发生,就要等待一定时间重新发送。而多信道是在信道容量不够的情况下增加信道容量避免冲突的方法之一,不同用户随机选择信道可以同时发送数据从而规避冲突,增加网络吞吐量,理论上在多信道环境下使用CRT序列是使用户在确定发送的情况下在随机选择信道,只有在两个用户都确定在同一时隙发送数据包,并且选择同一信道的情况下才会发生碰撞,这个可能性会大大减少。
2.2 构造方法
基于多信道跳频网络的CRT序列利用余数定理建立二维矩阵和一维数组之间的对应关系,假设一个p×q的矩阵:
其中p和q互质,与矩阵A对应的包含pq个元素的双射映射的一维数组为b=[b0,b1,…bpq-1],这两个数组元素之间的对应关系为
这里i mod p表示i对p取模,即为i除以p以后的余数。我们将数组b称为CRT匹配,可以很自然地得到,CRT匹配是一种线性映射,即:
为了详细说明,我们考虑一个时间指标(0,1,2,…,14)作为一个整数序列,其中 L=15,p=3,q=5。通过双射映射,得到二维整数序列为
当(0,1,…,14)循环位移成(14,0,1,2,…,13)则对应的数组为
可以注意到第二个数组可以通过对第一个数组向右循环位移并且向下平移一行而得到。
定义二维数组的汉明互相关为
很容易证明这样对二维数组互相关的定义是跟一维数组极其相似的,即:
其中 τ1= τmod p且 τ2= τmod q。
下一步,就要确立序列的特征集。构造协议序列,主要确立序列中1的位置,也就是用序列的特征集表示。对于CRT序列,其特征集定义为
其中g是生成数,且g=2,3,…,p。
移动一个周期序列τ个单位就等于转换其协议序列 τ个单位,设一个序列{0,1,…,L-1}为ZL,设L是ZL的一个子集,而且τ属于ZL,我们将经过τ转换的L记为
就特征集而言,a(t)和 b(t)的汉明互相关等于:
第三步就是构造CRT序列了,行和列的矩阵和数组分别为{0,1,…,p-1}和{0,1,…,q-1}。对于互质的p和q以及g∈ZL,我们定义:
其中 Gp,q就是p×q的矩阵,标记法(g,1)t意味着Gp,q中t个(g,1)位置上的数的和,即:
每一列向下移动g个单位,所以 Lg,p,q是由g产生的,则对于CRT序列,如果g=0,1,… ,p-1,则 CRT序列是由 g 产生的,记为 sg,p,q(t),而且这是一个长度为L的二进制序列,写为
刚刚例子中的特征集转换为CRT序列为
S0(t):10010 01001 00100
S1(t):11111 00000 00000
S2(t):10010 00100 01001
即用bi=(i mod p,i mod q)0 ≤ i< pq,也就是i从 0~14,如果bi∈Lg,p,q,则相应的 CRT 序列第 i+1位置上就是1。
3 基于多信道跳频网络的CRT序列仿真
在本文中运用Matlab对随机接入协议和CRT协议控制下系统的平均吞吐量、最差吞吐量,平均时延、最差时延进行仿真,并对两种方式进行比较,找出更能增大网络吞吐量,减少时延的一种。对于网络负载,取了10,15,20,25,30,35,40,45,50这9种情况设置节点数从小到大变化,因为有设置随机时延补偿,所以每一次的吞吐量和时延会不同,程序中通过10000次的运行,找出其中的最差值和平均值。对于多信道的情况设置了3信道与单信道进行对比,不管是随机接入还是CRT序列,理论上多信道都会一定程度上增大系统吞吐量并且减少时延的。
在程序中对协议序列的产生和随机访问序列的产生分别进行编写,因为最多有50个节点,p就要取大于 50的质数,因此 p=51,q=2p-1=101,L=p*q=5151,因为CRT序列的负载因子fduty=1/q=1/101,为了准确比较其与随机接入协议性能的差别,将随机接入协议的发送概率也设为1/101。并且因为每个节点产生的随机时延都是不同的且相互独立,则用一个数组对这些节点分配随机数。其中对信道的选择是随机的,冲突的计数为如果有多于一个节点产生的随机数(信道选择)相同,意味着占用同一信道,就对冲突次数一次。冲突的产生意味着传输的失败。
系统吞吐量定义为在一帧中成功发送数据包的时隙数跟总时隙数的比值,因此吞吐量成为衡量传输效率的一个标准,若一个通信网络的吞吐量越大,就意味着传输效率越高。因此在本课题中对ALOHA协议和CRT协议的平均吞吐量和最差吞吐量进行仿真,看在10000次实验中两种协议的平均性能好坏,以及在10000次随机时延产生中造成的系统最差情况,及传输成功次数最少的情况。
系统的时延是指从序列中随机一个值开始到下一次成功传输信息之间的等待时间。如果冲突过多则两次成功之间的时间就会很长,则从时延方面也可以衡量网络的竞争及性能。在本次仿真中计算的是两次成功传输之间时间延迟,平均时延就是对10000次实验求平均值,最差情况就是10000次实验中时延最大的一次。
4 仿真结果分析
4.1 平均网络吞吐量
在平均吞吐量仿真中共有2幅图,分别是信道数为1、3的结果。每幅图x轴是节点个数,y轴是吞吐量大小。
1)当信道数为1时
图2 信道数为3的平均网络吞吐量
结果分析:
图1对比了单信道下随机接入协议和CRT序列10000次实验中平均吞吐量随节点数的变化情况。从结果中可以看出,当单个节点负载一定时,随着网络中节点数的增加,网络负载增加,网络吞吐量也增加。因为负载较轻,且序列协议和随机协议负载因子相同,都为1/101。因此在平均情况下,二者吞吐量几乎重叠。不过,如果没有加入随机时延,在CRT序列控制下,只允许一个用户在一个时隙中传输信息,不会冲突,但是随机时延打破了CRT序列分布。
2)当信道数为3时
图2对比了信道数为3情况下随机接入协议和CRT序列10000次实验中平均吞吐量随节点数的变化情况。当单个节点负载一定时,随着网络中节点数的增加,网络负载增加,网络吞吐量也增加。因为负载较轻,且序列协议和随机协议负载相同,而且随机接入和CRT的负载因子相同,因此在平均情况下,二者吞吐量几乎重叠。从以上两幅图中还可以看出,随着信道数的增加,平均吞吐率也在增加,说明多信道可以提升平均网络吞吐量。
图1 信道数为1的平均网络吞吐量
4.2 最差网络吞吐量
1)当信道数为1时
图3 信道数为1的最差网络吞吐量
结果分析:
图3对比了信道数为1情况下随机接入协议和CRT序列10000次实验中最差情况吞吐量随节点数的变化情况。当单个节点负载一定时,随着网络中节点数的增加,网络负载增加,网络吞吐量也增加。因为CRT序列在设计时就是尽量避免碰撞,所以随机情况下碰撞的概率更高一些。在最差情况下,随机协议的吞吐量要低于序列协议的吞吐量,成功传输的信息包相对CRT序列要少。
2)当信道数为3时
结果分析:
图4对比了信道数为3情况下随机接入协议和CRT序列10000次实验中最差情况吞吐量随节点数的变化情况。当单个节点负载一定时,随着网络中节点数的增加,网络负载增加,网络吞吐量也增加。因为随机情况下碰撞的概率更高一些,所以在最差情况下,随机协议的吞吐量要低于序列协议的吞吐量。
图4 信道数为3的最差网络吞吐量
5 结语
对于多信道跳频网络中CRT序列的应用,从仿真结果来看,多信道的CRT序列性能要优于多信道的随机接入序列,所以目前看来有很好的应用前景。应用CRT序列有助于优化有较多负载情况下的网络吞吐量以及传输时延,减少冲突发生的概率。而且跳频通信具有抗干扰、抗衰弱能力,可以在战术无线电通信中得到广泛应用。对于民用方面,GSM系统首先采用跳频技术抵抗多径干扰。家庭射频和蓝牙技术也来采用跳频技术抵抗工业干扰,将多信道跳频技术与CRT序列相结合更能优化网络性能,提升网络容量。