基于多碰撞区域水声网格拓扑时隙调度研究

陈 国 璐

(哈尔滨工程大学 信息与通信工程学院， 哈尔滨 150001)

许多海洋科学、工业和军事应用可能需要部署水声传感器网络进行传感和监测[1].由于使用单个线性单播网络存在覆盖范围过小的特点，当涉及的区域很大时，可以考虑采用多跳中继的多线网格拓扑.从而实现大范围的覆盖.

由于水中声速慢，水声通信网络的传播延迟通常比较大，应用于陆地通信的握手机制和基于确认重传机制在水声通信网络的各种性能都会受到影响[2-5].因此本文将研究基于调度MAC协议而不是随机访问MAC协议.传统的调度时分多址(TDMA)在水声网络中存在信道利用率不高的问题，本文将重点研究文献[6]提出的一种基于大传播时延的MAC协议.

基于大传播时延传输调度MAC协议实际上是利用干扰重叠与空间复用机制.由于水下传感器是半双工工作模式，节点在工作时会处于发送、接收和空闲三种状态中的其中一种.我们将传输时间划分为若干个时隙，每个节点在不同的时隙改变自己的通信状态.

合理的调度使得大传播时延的性质可以充分的利用信道，提高吞吐量.当拓展到多节点的特定拓扑时，会有多个节点在同一时隙并发传输，就需要复杂的调度约束条件和调度算法来避免节点间的干扰.使用该机制的MAC协议一般有Super-TDMA[7]和DOTS[8].本文将在Super-TDMA协议框架下对网格网络的时隙调度进行研究.

Super-TDMA是为特殊结构的网络而设计的MAC协议，例如网格网络拓扑[9]、线性网络拓扑[10]和环状拓扑[11].将数据包传输时间和时隙长度设置为与节点之间的传播延迟相同[12].可以将Super-TDMA协议运行过程按时间概括如下.

1)网络初始化：需要获取节点的位置信息计算节点间的传输时延，计算其归一化时延矩阵.初始化阶段还需要统计网络的基本信息，如时隙长度、节点传输速率、数据包的长度、节点间的距离、节点的干扰范围等.

2)计算调度矩阵：将计算好的归一化整数时延矩阵、统计好的网络信息以及网络对调度矩阵的要求建立节点传输的约束条件，根据节点间的约束条件设计调度算法，得到传输调度矩阵.

3)传输数据包过程：各节点根据节点的调度矩阵和保护时间在每个时隙对节点的收发数据包进行控制.最终实现每个节点无冲突传输通信.

1.1 归一化时延矩阵

我们对一个线性N节点网格网络进行分析，其中，每对节点(i,j),∀i≠j且i,j=1,2,…,N都具有传输延迟，假设其为Dij.这样可以得到每个节点到其他节点的传输延迟.假设相邻节点的传输距离为d，相邻节点的传输延迟(即TDMA的时隙)我们定义为τ=d/c，在仿真中的数据包传输持续时间同样设置为τ.这样可以定义一个叫做时延矩阵D来表示网络的几何形状，我们其中时间以时隙长度τ为单位，其中的Dij项由式(1)得出：

(1)

其中：vi是节点i在3的位置矢量，c是信号传播速度.最大的传播延迟G=maxi,jDij表征网络的物理大小并且cτ被称为相邻节点的距离.

图1 三节点线性网络Figure 1 Three node linear network

对于如图1所示的3个节点线性单播网络，我们将时隙长度为节点间的传输延迟，其归一化时延矩阵见式(2).

(2)

由于Super-TDMA需要在选取合理的时隙长度下，节点间的传输时延都为整数，因此还要将有理数归一化矩阵D进行四舍五入整数化.

1.2 碰撞域

我们假设归一化节点通信范围为Rc=1，归一化干扰范围为RI=k,k∈Z+.其中k代表的是干扰范围与节点通信范围的比值，也就是碰撞域.其中Rc=1和RI=k，1

图2 规则节点多线网格网络Figure 2 Multiline grid network with regular nodes

在大传输延迟的水声环境下，引入一个规则的N节点网格网络，其中的每个节点用i(1≤i≤N)来表示.设η(η≥1)表示网格的列数.来自源节点的消息垂直向下中继传输，直到他们分别到达最终目的的节点.本节研究的网格网络是在同一列上的每个节点之间具有单位间距的网络.而相邻列之间的距离设为同一列的节点间距离的k倍，其中k代表干扰域.所以在网格网络的架构中，纵跨为一个单元，横跨为k个单元.网格网络的拓扑如图2所示.

1.3 时隙调度矩阵与吞吐量

将仿真的时间由连续的时隙长度的时间片组成，并基于时分多址(TDMA)应用周期性时隙计划.将节点枚举为={1,2,…,N}，同样将时隙枚举为T={1,2,…,T}，这样可以定义一个N×T的S矩阵来表示各节点在不同时隙下发送或接收的调度安排，称其为调度矩阵.调度矩阵中的Sjt表示节点j在时隙t的通信状态.如果Sjt=i>0，则节点j在时隙t内向节点i发送数据包.如果Sjt=i<0，则节点j在时隙t内接收节点i发送的数据包.如果Sjt=0，则节点j在时隙t内保持空闲.

由于是基于TDMA应用周期性时隙计划设计出的传输调度矩阵，所以存在周期T使得传输调度矩阵满足Sj,t+T=Sjt，所以可以使用S(T)矩阵代表具有周期性的传输调度矩阵.即：

(3)

由式(3)可知，传输调度矩阵是周期拼接而成的，而根据周期的开始时间的不同得到的调度矩阵也不相同，但是他们表达的是同一传输调度矩阵.对于给定的网络拓扑，将吞吐量定义为：

(4)

其中：β是传输速率，Lp是数据包的长度，Ls是时隙长度，如果数据包是全尺寸数据包，即Lp=Ls.网络平均归一化吞吐量由式(5)所示：

(5)

为了说明该模型，考虑单向业务流线性单播网络在干扰范围是传输范围的两倍情况下，是怎样利用大传播时延来提高网络吞吐量.如图2所示，网络的时延矩阵中的D12=D23=D13=τ，时延矩阵由式(2)所示，其达到最大吞吐量的周期调度矩阵S3×4由式(6)所示.

(6)

对于每个半双工节点，调度表能确保来自其他节点的干扰在该节点正在发送数据包时才到达.我们设数据包长Lp等于时隙长度Ls=τ，在每个周期T=4τ中接收4个数据包，归一化吞吐量为(4βτ/β)/4τ=1.

网格网络每一列节点都会将自己的源目的地址消息独立地转发到最终目的地，每列的目的地址只能接收自己列的源节点.我们分析最优的时隙表(可实现最大吞吐量)SN×T可实现的最大吞吐量.单向业务流的线性网格网络每一列中会有N/η个节点且每一列的数据流是单向的，从节点1,2,…,η发出的一条消息一跳接一跳地转发，直到它们分别到达最终目的地节点N-η+1,N-η+2,…,N.归一化网络吞吐量Y是单位时间内网络中所有节点成功接收到的信息比特总数.假设源节点发送了c个消息，中继节点负责转发消息，单向业务流的网格网络的标准化吞吐量见式(7).

(7)

每个中继节点至少在T内接收和发送了一个消息.源节点不接收消息，目的节点不发送消息.所时隙表以共存在的η((N/η)-1)正项、η((N/η)-1)负项和2η(T-1)零.

在单向业务流线性单播网络中，节点j向节点(j+1)发送消息后每个时隙的节点状态.当节点j在时隙t发送，节点(j+2)在时隙(t+2)内不能收到任何消息，因为节点(j+1)应该在时隙(t+1)接收j节点发送的消息，半双工约束不允许节点在接收时进行传输.当节点(j+2)在时隙(t+2)期间发送时，节点(j+3)将在时隙(t+3)接收消息，所以节点{j+2,j+3,…,j+k-1}将会使节点j在不同的(k-2)时隙内保持空闲状态.

所以单向业务流的线性网格网络的最优时隙表会存在η(k-2)((N/η)-2)个零.假设源节点发送c个消息，可以得到：

2cη((N/η)-1)+2η(T-c)+

cη(k-2)((N/η)-2)≤NT

(8)

上式化简可得T≥kc，∀N>2η,将其带入式(8)中，可以得出双向业务流的线性单播网络的平均吞吐量，满足：

(9)

上式归一化平均吞吐量上限基于k≥2时成立，当η=1时，网格网络也会变成线性网络.

由于节点工作模式是半双工的，其传输状态还存在其他节点的干扰.单向业务流的线性网格网络的节点传输约束条件可写成下式：

(10)

在设计时隙表时由式(8)所示，设计调度矩阵的最小周期应该为k(k>2)，当k=2时，调度矩阵的周期应为4.首先创建初始零矩阵，根据约束条件更新每个节点的传输状态，得到最优时隙表.设计网格网络时隙调度矩阵的算法流程图如图3所示.

从图3可以看出首先建立一个N×T的零矩阵，对头节点进行初始化状态更新.在更新节点状态时要确保当前节点的传输状态不受其他节点的干扰.至此输出一个可实现该业务模型的N×T的调度矩阵.

图3 设计网格网络时隙调度矩阵的算法图Figure 3 Algorithm for designing grid network timeslot scheduling matrix

为验证启发搜素算法得出的调度矩阵能使得单向业务流线性单播网络逼近理论吞吐量，在仿真时假设每个传感器节点的时钟同步并且忽略物理层传输数据包时的丢包和时隙保护的开销下，仅考虑信道冲突带来的吞吐量的损失.在饱和负载的情况下，单向业务流的线性单播网格网络吞吐量在不同列数与不同干扰范围下的吞吐量如图4所示.

图4 在不同列数、不同干扰域(k)下的归一化吞吐量Figure 4 Normalized throughput under different number of columns and different interference domains (k)

仿真图中的k表示的是冲突域，仿真图中的直线代表单向业务流线性单播网格网络在不同干扰域(k)的理论吞吐量，图中的圆点等图标代表的是仿真吞吐量.仿真值与理论值会有0.01左右的差距.这是因为调度矩阵在仿真时间内没有形成闭环传输，即仿真时间开始时网络中没有数据包的传输和仿真时间结束后网络中仍有数据包没有到达目的节点.以上原因造成仿真时的归一化吞吐量与理论的差距.仿真结果验证了所提出的算法可以有效地确定双向业务流线性单播网络的最佳调度，从而实现最大可能的吞吐量并渐近逼近其吞吐量上限.

由以上分析可得，为了使网络中影响数据包的排对时延与流量负载无关，只与调度算法的优劣有关，需要设计合适的流量强度.需要根据调度矩阵的周期来确定数据包的产生间隔，每个周期产生一个数据包可以保证数据包的排队时延只与算法的优劣程度有关.图5表示的是数据包在列数为4时的排队时延与端对端时延.

图5 在列数为4时、不同干扰域(k)下的排队时延与端对端时延Figure 5 Queuing delay and end-to-end delay under different interference domains (k) when the number of columns is 4

图5中影响网络中数据包的排队时延与流量负载无关，只与调度算法的优劣有关.因为在不同干扰范围下的传播时延相同，端对端时延的差异主要是由调度算法为了避免节点在数据包传输时碰撞而在特定的时隙发送数据包而造成的排队时延.当k=3时，其排队时延几乎为0，所以当节点设置的干扰范围为传输范围2倍(k=2)时，下一跳节点由于信号太弱不能成功正确解码接收数据包，需要增大信号强度，扩大干扰范围.这时干扰范围为传输范围3倍(k=3)的性价比是最高的.由图5(B)可知当干扰域为2时与干扰域为4时的端对端时延大体相同，但由图4(A)可知，两者的吞吐量相差将近1倍以上.

本文利用水声大传输时延特性的Super-TDMA协议作为理论框架，从利用大传播时延的特性提高网络吞吐量和降低端对端时延的角度出发，结合水声传感器网络干扰范围可变的特点，在干扰范围可变的情况下推导出线性网格拓扑在不同业务模型下时隙调度的吞吐量上限，并设计了达到单双向业务模型吞吐量上限的时隙调度矩阵.使用OMNeT++软件搭建Super-TDMA协议框架对其时隙调度算法进行仿真.通过仿真结果表明，在网络流量负载饱和的情况下，设计的时隙调度矩阵可以达到所证明的吞吐量上限.