多跳分簇自组网络的最优簇内跳数分析

张文庆， 李旭， 黄文俊

(北京交通大学 电子信息工程学院, 北京 100044)

0 引言

移动自组网络在分簇结构下可将网络划分为多个称为簇的小区域，缩小路由洪泛范围，使得路由开销大大减少，减少节点移动对网络结构的影响，进而克服平面网络扩展性差的问题，因此成为自组网络领域的一个研究热点[1]。

截止目前，国内外学者对多跳分簇路由协议已进行了大量研究。Max-Min[2]是被提出的第1个多跳分簇算法，该算法提出了在2k轮多跳控制信息交换中实现k跳分簇的算法。DiLoC分簇算法[3]对簇内跳数没有任何限制，与锚节点(簇首)连接的节点都可以加入该簇。文献[4]提出了一种稳定的k跳分簇路由算法，该算法从邻居维护和簇首选举方面进行改进，增强了网络拓扑的稳定性。文献[5]提出一种用于认知无线电网络的k跳分簇算法，并通过仿真分析表明该算法能够提升网络的连通性和鲁棒性。以上文献从协议设计角度对多跳分簇进行了研究，但对协议所适用的簇内跳数取值并未展开研究。

当簇内跳数过大时，簇内节点数量增多，簇头节点负担增加，且簇的维护开销增加，多个节点竞争有限资源，因此节点的平均吞吐量降低[6]；当簇的半径过小时，会导致簇的数量过多，网络结构易发生变化，且邻簇间干扰增加，网络容量下降，节点的平均吞吐量下降。

文献[7]研究了移动自组网络分簇路由协议中簇尺寸对簇的稳定性和维护开销的影响，提出了基于优化分簇的混合分层路由(HOCR)协议，但该文仅从路由层面研究了簇尺寸对网络性能的影响。文献[8]研究了Wimax网状网络中的分级式跨层路由，考虑了簇内簇间的路由和时隙分配，并分析了簇大小对网络性能的影响。但该文中的簇尺寸是簇内节点个数，所研究的网络内节点个数较少，且未考虑网络干扰。文献[9]研究了云小区网络中信道状态信息延迟对吞吐量增益的影响，并基于均匀泊松点过程推导了信号干扰噪声比，以网络和速率最大化为目标，分析了最佳簇尺寸。文献[10]分析了媒体介入控制(MAC)层为码分多址(CDMA)接入的无线传感器网络簇内簇间干扰，并分析了簇尺寸对簇间干扰和网络容量的影响。但以上两个文献都未考虑路由层的簇维护消耗。

本文针对大规模多跳移动分簇自组网的簇内跳数优化问题，综合考虑网络层路由消耗和MAC层帧结构设计来研究簇内跳数对网络吞吐量和网络信道利用率的影响，利用硬核泊松点过程(HCPP)模型分析网络干扰，并以吞吐量最大化为目标，以信道利用率为约束，得到最优的簇内跳数，最后研究了路径损耗系数和节点密度等关键参数对最优簇内跳数的影响。

1 系统模型

考虑1个有N个节点的分帧分时隙无线网络(见图1)。节点的空间分布服从密度为λp的泊松点过程。节点的通信半径为r，最大移动速度为vmax.节点的MAC层采用协调分布式调度模式，网络层采用分簇拓扑管理机制。全网节点使用同一频点收发消息，系统总带宽为W. 记E(·)为期望值函数。

1.1 MAC层调度

在协调分布式调度模式中，1个MAC层帧分为控制子帧和数据子帧两部分，子帧又被划分为多个时隙。每个节点的MAC层通过收发调度信息维护h跳邻居信息。MAC层采用Mesh Election机制实现控制时隙调度，以保证控制消息的无碰传输；数据时隙通过控制消息的3次握手机制实现预约调度[11]。

设控制子帧的时隙个数为C，单个控制时隙最大可传输比特数为lc，控制时隙单位时间比特容量为Rc，则1个控制时隙的时长为tc=lc/Rc；数据子帧的时隙个数记为D，单个数据时隙最大可传输比特数为ld，数据时隙单位时间比特容量为Rd，则1个数据时隙的时长为td=ld/Rd. 记1个帧的时长为tf，其等于控制子帧与数据子帧的时长总和，

tf=Ctc+Dtd.

(1)

1.2 网络层分簇

网络层根据分簇拓扑管理机制，将网络划分为簇。簇由一些相互邻近的节点组成，包括1个簇首节点和若干个簇内成员节点。为方便起见，规定簇首节点维护的邻居跳数与MAC层所维护的邻居跳数h一致。由于分簇机制的作用，使每个簇首所维护的h跳邻居都不会成为新的簇首，分簇机制同样与HCPP的稀释过程一致，即簇首节点定期发送簇内广播报文，簇内成员节点收到广播报文后会发送给簇首节点响应报文，从而实现簇的形成和维护。

假设1个簇的簇首节点均处于簇的中心，则单个簇的覆盖范围可以看作以簇首为中心、簇半径R=hr的1个圆，由此得到单个簇内的成员节点个数为

nm=λpπR2=λpπh2r2.

(2)

在分簇机制作用下，网络中的发送节点分布不再服从泊松点过程。HCPP能够紧密结合分簇机制，对完全随机分布的节点进行一定程度的稀释，准确描述出网络中干扰节点的分布。其主要思路是：如果两点之间的距离小于1个给定值，则按一定规则去掉其中的1个点，最终得到的就是HCPP. 因此，网络层簇首节点的分布与HCPP完全契合，得到簇首节点密度[12]为

(3)

根据全网节点数N和节点分布密度λp，以及分簇机制得到的簇首节点密度λl，可以求出在全网覆盖范围内的簇首个数为

(4)

每个簇首对应着1个簇，因此网络中划分得到的簇的个数等于簇首节点个数。求节点之间的平均跳数距离。根据文献[13]结论，1个具有N个节点的网络，单个节点的一跳距离覆盖范围内的节点个数为n，则节点间跳数的数学期望为

(5)

假设节点的单跳距离为节点通信半径，即dinn=r. 根据(5)式可得簇内任意1个节点与簇内其他节点的平均转发跳数为

(6)

由于单个节点的一跳距离覆盖范围内必须有至少1个邻居，节点密度需要满足以下条件：

λpπr2≥2.

(7)

在完成网络簇划分后，簇首节点共同组成1张簇级网络。在簇级网络中，如果两个簇首节点间距离在(R,2R]范围内，则两个簇相邻。对于1个簇首节点，本文近似认为与其距离第i(1≤i≤h)跳的节点都处于以其为中心、半径范围为((i-1)r,ir]的圆环内。记距离1个簇首第i跳的节点所在的圆环面积为

Si=πi2r2-π(i-1)2r2=(2i-1)πr2，

(8)

由此可以求出两个互为相邻簇首的节点之间的平均距离dint，即簇级网络一跳距离的数学期望为

(9)

根据(5)式，在簇级网络中1个簇首与其他簇首之间的平均转发跳数距离为

(10)

2 网络性能分析

下面首先利用HCPP模型对协调分布式调度模式下的Mesh Election机制与3次握手机制进行建模分析，推导出MAC层控制时隙和数据时隙的信号干扰比和容量模型。然后分别从簇内和簇外两个角度，分析业务量以及调度数据时隙和维护簇结构所需要的开销。最后结合达到最大吞吐量条件以及由信号干扰比得出的投递率，得到最大吞吐量的闭式解。

2.1 干扰与容量分析

2.1.1 Mesh Election选举机制

由于节点维护h跳邻居的调度信息，在Mesh Election选举过程中，每个节点都将与h跳范围内的邻居节点展开选举竞争，最终竞选成功的发送节点周围会形成1个半径为R=hr的圆形干扰清除区域。其他竞选成功的发送节点将成为干扰节点，其分布与稀释半径为hr的HCPP完全契合。由此得到选举机制下发送节点密度[12]为

(11)

假设两个发送节点的距离为s，则它们各自圆形干扰清除区域的联合面积大小为

(12)

经过选举算法对原网络节点的密度进行稀释后，与接收端相距s的节点能被保留成为发送节点的概率[14]为

(13)

为了反映两节点的相互作用关系，引入两两节点间的空间相关函数[12]g(s)，定义为

(14)

设定发送节点为原点O，d表示接收节点与发送节点的距离，φ表示接收节点所处的方向。则接收节点遭受的干扰强度I的数学期望如下：

(15)

式中：l(s)=s-α为路径损耗函数，α为路径损耗指数。

将节点按空间相关性划分为hr≤s<2hr和s≥2hr两部分，则平均干扰强度E(I)为两部分干扰强度的叠加，即

E(I)=E(Ihr≤s<2hr)+E(Is≥2hr)，

(16)

在区间[2R,∞)上，节点互在彼此的排斥区域之外，即两个节点在空间上独立无关，由此得到选举机制下接收端信号干扰比SIRme的数学期望值为

(17)

控制消息容量RC由选举机制下的SIRme和香农公式计算得到：

RC=Wlog2(1+SIRme).

(18)

2.1.2 3次握手机制

分别以发送节点和接收节点为圆心、半径为hr作两个圆形，对于两个圆形并集范围内的其他节点进行稀释，不允许这些节点成为发送节点，从而实现MAC层3次握手机制的干扰消除。发送与接收节点形成的两个圆形并集的面积Ao为

(19)

由HCPP的密度公式[12]，代入Ao可以得到3次握手机制下的干扰节点密度为

(20)

如图2所示，假设坐标为x1的干扰发送节点s1位于极坐标平面原点O处，对应的接收节点位于s1的0°方向，用(s,β,θ)表示网络中的另一干扰通信对的位置；干扰发送节点s2位于原点O的β方向上的x2坐标处，对应的干扰接收节点位于s2的θ方向上。则这两个通信对的干扰清除区域联合面积A只是(s,β,θ)的函数。

显然，如果s2与s1的距离小于R，或s2与s1的接收节点的距离小于R，则这两个通信对不可能共存。同理，如果s2的接收端位于s1通信对的干扰清除区域内，则这两个通信对共存概率也为0. 除上述情况之外，两个通信对共同存在的概率用(21)式计算：

(21)

为简化符号起见，记余弦定理求边公式为

(22)

结合上式以及对相关函数g(·)的定义，上述两个通信对的相关函数整理如下：

(23)

根据文献[14]，得到3次握手机制接收端信号干扰比SIRth的数学期望值为

(24)

数据消息容量RD由3次握手机制下的SIRth和香农公式计算得到：

RD=Wlog2(1+SIRth).

(25)

2.2 业务量分析

对于需要多跳传输的数据业务，不仅需要源节点的发送，还需要中间节点的转发。为方便起见，假设每个节点均以相同的本地业务包到达速率λ(单位为个/s)发送业务，每个数据包恰好可用1个数据时隙发送。记1个簇单位时间内所需发送的总数据业务量为M，分为簇内业务量Minn和簇间业务量Mint两部分，

M=Minn+Mint.

(26)

假设1个节点的簇间业务量与总业务量的比例为γ，用以表征簇间业务需求的指标。当每个节点都与整个网络内所有其他节点有相同的业务通信需求时，业务比例γ等于簇外节点个数与全网节点个数的比值，

γ=1-nm/N，

(27)

单个簇的簇内业务量等于该簇内所有节点的簇内业务量总和：

Minn=nmλhinn.

(28)

单个簇的簇间业务需要由源节点先汇聚到簇首，再由簇首指定路径后，由路径上的网关节点和簇成员节点转发到目的节点所在簇的簇首，最后转发到簇内目的节点。源节点汇聚到簇首的业务与目的节点所在簇簇首转发到目的节点业务仍属于簇内业务，因此簇间业务只需要统计簇首之间转发的业务量。故单个簇的簇间业务量为

Mint=nmγλhint.

(29)

综上所述可得1个簇单位时间内所需发送的总数据业务量为

M=nmλ(hinn+γhint).

(30)

2.3 开销分析

本文分析的开销主要包括MAC层调度数据时隙开销和路由层簇维护开销两部分。下面分析这两部分的开销。

2.3.1 调度数据时隙开销

调度数据时隙的消耗产生在每次预约数据时隙时，需要3个控制时隙来分别发送请求-授权-确认消息，完成3次握手预约流程。设τ为节点单次能够预约到的数据时隙个数，可以得到恰好调度1个帧内D个数据时隙所需占用的控制时隙个数为

(31)

2.3.2 簇维护开销

1个簇的维护开销可以分为簇内维护开销Oinn和簇间维护开销Oint两部分。记单位时间内簇的总维护开销Oclu为簇内和簇间维护开销之和：

Oclu=Oinn+Oint.

(32)

簇内维护开销是指单位时间内每个簇对自身结构的一次维护过程中所产生的平均控制报文个数，包括两个部分：簇首节点广播一次簇更新报文，所有收到簇更新报文的成员节点都将广播转发一次该簇更新报文；成员节点以单播形式向簇首回复响应报文。对于距离簇首节点第i跳的成员节点，回复响应报文至其簇首的转发过程将引发i个控制报文。根据(8)式，可以求出距离簇首第i跳的成员节点个数qi=λpSi. 设簇首节点发送簇更新报文的频率为finn，根据文献[15]得出网络的一跳链路平均保持时间为

(33)

式中：v1和v2表示一跳链路上两节点的运行速度。则对于1个h跳簇，其簇内维护频率应该设为簇内h跳链路的保持时间，以保证簇首在链路发生变化时能够及时维护簇结构。因此簇内维护频率finn=h/Tlink. 由此可以得到每个簇维护一次簇结构的开销为

(34)

簇间维护开销是指1个簇与网络中其他簇之间对表驱动路由进行维护的开销，与以下3个因素相关：簇间路由维护beacon的广播频率fint、簇首个数nl以及簇级网络中1个簇首与其他簇首之间的平均转发跳数距离hint. 簇间beacon的广播频率fint是簇首为了维护簇级网络中到其余各簇首的路径而进行广播的速率，应设为边界节点移动出簇的时间倒数，即fint=1/Tlink，因此得到簇间总控制开销为

Oint=fint(nl-1)hint.

(35)

3 网络吞吐量分析

本文希望通过优化簇内跳数h，在保证信道利用率条件下，最大化单个网络节点的本地业务到达速率λ：

(36)

式中：η为单个簇内的信道利用率；η0为期望信道利用率。

在时分多址(TDMA)网络中，由于1个帧的长度有限，控制时隙和数据时隙的个数设定将直接影响网络性能。如果控制时隙所占比例过大，则会导致数据时隙即使全部被占满仍然不能满足调度所需的情况；如果每个帧中的控制时隙过少，则数据时隙将相应地增多，在满足调度所需时隙的情况下仍有剩余。当然也存在一种极限情况，使得数据时隙恰好被占满，既满足调度需求又没有空闲时隙，控制时隙恰好满足调度数据时隙以及簇维护的消耗。这个临界情况就是本文所希望设计的最优帧结构，即要达到最大网络吞吐量需要满足两个条件：控制时隙恰好全部用于发送消耗；所有数据时隙恰好全部被占用。将这两个条件转换成表达式的形式，即：

1)簇维护消耗Oclu+调度所有数据时隙消耗Oschd=控制时隙的个数C；

2)簇内业务量Minn+簇间业务量Mint=最大预约时隙全部数据量D.

对应地，可以得到1个方程组：

(37)

式中：Ptc和Ptd分别为控制时隙和数据时隙的传输成功概率。根据2.1节，可以得到四相相移键控(QPSK)调制方式下控制时隙和数据时隙的误码率分别为

(38)

(39)

则控制时隙和数据时隙的传输成功概率分别为

Ptc=(1-Pec)lc，

(40)

Ptd=(1-Ped)ld.

(41)

求解上述方程组，可得节点最大平均吞吐量(单位为bit/s)为

(42)

则单个簇内的信道利用率(单位时间内发送数据的有效时间)为

(43)

根据文献[11]和文献[14]可知(36)式的模型问题类型是NP-hard问题，本文只分析了其数值解。

4 仿真结果

4.1 参数设置

下面使用MATLAB工具对提出的性能模型进行分析，通过仿真结果对关系曲线图的变化趋势进行讨论，给出相应的物理意义和关键协议参数的选择方案。仿真参数设置如下：网络节点个数N=2 000，节点通信半径r=100 m，最大移动速度vmax=5 m/s，系统总带宽W=40 MHz，单个3次握手过程最大可预约时隙数τ=5，控制消息长度lc=3 200 bit，数据包长ld=8 000 bit，信道利用率期望值η0=0.75.

4.2 信号干扰比

信号干扰比反映了网络可靠性，也决定了网络容量。图3给出了控制消息与数据消息的接收信号干扰比变化情况。由图3可以看出：簇内维护跳数h越大，接收信号干扰比越高，这是因为簇内跳数越大，干扰消除的区域就越大，干扰也越小；在节点密度较小时，随着节点密度的增加，接收信号干扰比下降。在节点密度超过某个值时信号干扰比基本不变，这是因为在节点密度较小时节点间的距离较大，相互不在对方的稀释范围内；随着节点密度的增加，稀释后的密度也增加，对接收节点造成干扰的节点增多，从而信号干扰比降低；当整个区域都被稀释范围覆盖后，再增加节点密度，新增的节点都会落在稀释范围内而被稀释掉，因此稀释后的节点密度不变，即接收节点周围的干扰节点密度不变，信号干扰比保持不变。

在簇内维护两跳、节点密度上升至15个/km2时，控制消息接收信号干扰比SIRme已经下降至不足8 dB，数据消息接收信号干扰比SIRth下降至11 dB. 将簇内跳数扩大至3跳以后，控制消息信号干扰比能够提升至13 dB以上，数据消息信号干扰比提升至15 dB以上。

根据(7)式，原始节点密度需要满足λp≥2/(πr2)≈63.7个/km2，因此在后续仿真分析中，节点密度取λp≥70个/km2，以满足节点间的连通性。

4.3 节点平均吞吐量

节点平均吞吐量反映了每个节点的平均发送业务能力，也是评价网络性能的直接指标。图4给出了节点平均吞吐量的变化关系图。由图4可以看出，当簇内跳数为2时，由于干扰太大，使得吞吐量几乎为0，在α=4簇内跳数为3跳以上时由于网络干扰不再是主要限制因素，簇内跳数越大，簇内的节点数增多，每个节点的平均吞吐量下降。当α=3时，簇内最优跳数为4跳。这是因为在路径损耗α增加时簇间的干扰会减小，此时可通过减小簇内跳数来减小簇内节点个数，从而增加节点的平均吞吐量。另外，吞吐量随节点密度的增加而降低。因为随着节点密度的增加，簇内的节点数增多，维护开销增加，且在信道资源有限情况下，每个节点分得的信道资源下降，造成节点有效吞吐量下降，所以降低节点密度也是增加节点平均吞吐量的一种有效方式。

4.4 信道利用率

信道利用率反映了信道被占用情况，也反映了网络的有效性。图5给出了信道利用率的变化情况。由图5可以看出，在达到最优跳数后，当节点密度较小时，由于网络负载未达到最大值，在节点密度增加时可通过优化帧结构设计来提高吞吐量，但在节点密度较大时，继续增加簇内跳数带来的额外开销使得信道利用率下降，而且节点密度越高，维护邻居的开销越大。当簇内跳数低于最优跳数时，由于簇间干扰太强，使得控制时隙的传输成功概率很低，需要更多的控制时隙来重新传送控制消息，因此信道利用率下降。当簇内跳数为2时，单个簇的信道利用率几乎为0.

由于信道利用率期望值η0=0.75，在α=3、λp=500个/km2时，虽然4跳时可以取得最优的节点平均吞吐量，但信道利用率最优值小于η0. 对此，可以通过降低节点密度、提升信道利用率来满足约束条件要求。

5 结论

本文综合考虑了网络层和MAC层帧消耗，利用HCPP模型分析簇间干扰，并以吞吐量最大化为目标，推导最优的簇内跳数，最后研究了影响最优跳数的关键参数。仿真结果表明：跳数越大、节点密度越小时，网络干扰越小；簇内跳数的最优值主要取决于路径损耗和节点密度，路径损耗增大且节点密度降低时，最优跳数减小，最大节点平均吞吐量增加。

本文重点在于分簇对链路干扰和网络性能的影响，对信道模型的处理比较简单，后续将考虑更加复杂的信道条件以及移动场景等非稳态因素。