从无线网络产生以来,时延问题就受到了广泛关注.目前,已在无线ad hoc网络和无线传感器网络中有很多相关的研究^[1,2].然而,已有的研究仅考虑了用户节点密度对网络时延的影响.不同于传统的无线网络,认知无线电网络所处的频谱环境是动态变化的,由此带来的网络连通状态变化会对时延产生极大的影响,对网络时延的分析需要建立在频谱特征分析的基础上.因此,如何分析动态频谱环境下的认知无线电网络时延,是一个亟待解决的问题.

本文将认知无线电网络时延的主要影响因素归结为两类:一类是动态频谱资源的影响,包括授权用户的活动和信道数量;另一类是节点密度的影响.下面分别对这些因素进行详细介绍.

(1) 授权用户活动的影响

在认知无线电网络中,授权用户拥有频谱接入的优先权,而认知用户只能在授权用户空闲时,择机进行频谱接入.当授权用户出现时,认知用户必须让出借用的注册信道,切换到其他可用的信道.频繁的频谱切换将会产生很大的切换时延.因此,由授权用户活动导致的频谱动态变化是认知无线电网络时延变化的一个重要原因.

(2) 信道数量的影响

传统无线网络采用固定单信道的频谱接入方式,而认知无线电网络采用更加灵活的频谱接入机制,用户可以使用整个频段的信道^[3].当信道数量很小时,可供用户选择的机会就少.如果侦测不到可用信道,用户只有中断传输等待可用信道出现,从而增加信息传输的时延;反之亦然.因此,注册信道数量也会对网络时延产生影响.

(3) 节点密度的影响

认知无线电网络中的节点密度又可细分为授权用户密度和认知用户密度,它们都会对网络时延产生影响.当授权用户密度小时,受其影响的区域较小,留给认知用户使用的频谱机会相对较多,认知用户的传输时延较小且与认知用户密度成反比;当授权用户的节点密度很大时,影响范围较大,频谱机会就少,从而导致网络时延的增加;当授权用户密度足够大时,没有频谱机会可用,网络时延将趋近无穷大.

针对以上分析,本文致力于分析动态频谱环境下的大规模认知无线电网络时延的变化规律.首先,对动态频谱环境进行建模,该模型综合考虑了授权用户的活动以及信道数量对频谱环境的影响;其次,本文将动态频谱环境模型与首次通过渗流理论结合起来,研究了大规模认知无线电网络时延的伸缩规律,该规律通过提供更精确的时延与距离比的上限值来反映网络时延与用户活动、信道数量以及密度之间的密切联系.本文的相关结论可以对网络的整体规划进行指导,从而在总体上提升网络的性能.比如:在路由设计的过程中,依据网络传输时延合理地分配频谱资源,从而实现频谱资源利用率的最优化;在网络拓扑控制过程中,根据网络时延情况动态调整节点布署,从而达到网络覆盖的最大化.

本文第1节介绍相关工作.第2节描述网络模型和通信模型.第3节对动态频谱环境进行建模.第4节给出认知无线电网络时延分析的相关结论.第5节利用仿真实验对结论进行验证.第6节对全文进行总结和展望.

网络时延是在多跳无线网络中被广泛研究的关键问题之一^{[4, 5, 6, 7, 8]}.文献^[4,5]研究了在全连通状态下,多跳无线网络的传输时延的边界问题.Dousse等人^[6]研究了无线传感器网络中,非协调功率节省机制的消息传输延时问题,他们证明了传输延时与节点随机分布的位置无关,而与节点密度、传输距离以及节点激活和睡眠的时段等网络参数有关.在文献^[7]中,Kong和Yeh考虑到节点的移动性造成两个节点之间距离的增大,从而导致的链路中断对传输时延造成的影响.Zhao等人^[8]针对大规模无线ad hoc网络中不稳定的连接,对节点密度和传输延时之间的基本关系给出了一个更加精确的描述.文献^[9]利用图着色模型研究了网络拓扑结构对平均传输时延的影响.然而,以上研究都是针对传统无线网络的时延分析,没有考虑到认知无线电网络中动态频谱变化的情况.

随着认知无线电网络研究的日益广泛,针对提高频谱利用率的频谱共享和资源分配问题已经有了很多研究^{[10, 11, 12]}.但是,网络时延分析问题的研究还处于初级阶段.Ren,Zhao和Swami^[13]是最先研究认知无线电网络中的时延分析问题的,他们利用连续渗流的技术和理论来描述认知网络连通区域的特征,将认知网络划分为连通状态和次连通状态;在此基础上,通过将网络信息分发时延分析描述为一个首次通过渗流过程,分析在两种状态情况下时延与距离之间分别呈现次线性变化和线性变化.文献^[14]首先将授权用户的活动建模为一个稳态的ON/OFF过程,然后也给出了时延与距离比在两种连通状态下的伸缩规律.近年来,Liu等人^[15]依据授权用户和认知用户的密度标准,将大规模认知无线网络中的连通状态进行了更为细致的划分,分成了连通状态、局部连通状态和非连通状态,并给出时延和距离比值与用户密度的关系表达.文献^[16]通过构建认知无线电网络的虚拟骨干网来对网络传输时延进行分析,结果表明,在单播机制(unicast scheduling)下产生的时延与传输距离呈 线性变化,而在汇聚传输机制(convergecast scheduling)下的传输时延上限为

然而,上述工作存在如下两方面问题:(1) 都是在单一信道的场景下进行的;(2) 只描述了时延与用户密度的关系.在认知无线电网络中,需要更全面地考虑影响网络时延的因素,比如信道数目、授权用户活动等动态频谱特征,而这些特征也是认知无线电网络与传统无线网络的关键区别.

与前面的工作不同,本文充分考虑了频谱的动态性,通过对动态频谱环境进行建模来量化授权用户和信道数量等因素的影响,并结合用户密度一起分析大规模认知无线电网络的时延变化规律.

本文考虑主网络与认知网络在平面R²上共存的场景,两个网络都是利用几何随机图来建模^[17],其中,主网络建模为一个随机的圆盘图G(l_p,r_p),在该图中,假设所有的授权用户都有相同的传输半径r_p,每个授权用户使用的信道都由系统控制单元随机分配,授权用户按照密度参数为l_p的两维泊松点过程分布.同样,认知网络也建模为一个随机的圆盘图G(l_s,r_s),l_s和r_s分别代表认知用户的密度和传输半径.

定义1(关键密度). 在认知无线电网络中,授权用户和认知用户都有自己的关键密度:授权用户的关键密度是指能够使认知网络连通的最大的主节点密度;与之相比,认知用户的关键密度是指能够保证图G(l_s,r_s)连通的概率大于0的最小认知节点密度.例如,当时,如果,则G(l_s,r_s)处于连通状态;否则,G(l_s,r_s)处于次连通状态.本文将在后面的章节中阐述节点密度对网络时延的影响.

定义2(极大连通分支C_max). 这是指图G(l_s,r_s)中的最大连通子图.

定义3(连通概率Prob_¥(l_s)). 这是指图G(l_s,r_s)的极大连通分支拥有无穷大数量的认知用户的概率,例如:

Prob_¥(l_s)=Prob(|C_max|=+¥).

在传统的无线网络中,节点之间的距离和传输功率是决定通信的关键因素,两个节点只要在相互能够传输的距离之内,就可以建立双向连接.然而,认知无线电网络中的通信问题不同于传统的无线网络,认知用户面临的是具有差异性和时变性的频谱,不同的节点所能够使用的可用信道可能是不一样的;而且,频谱的可用性还随着授权用户的活动情况动态地发生变化.在认知无线电网络中,两个认知用户只有在双双都在相互的通信范围之内,而且都有至少一个共同的可用信道的情况下才能够通信.在图 1中,有一条从源节点S到目的节点D的路径.如果一个授权用户出现在正被认知用户使用的信道上,则该认知用户必须立即放弃该信道,中断传输.因此,认知无线电网络中的通信不仅仅与传输距离和传输功率有关系,还与信道的可用性有很大的关系.本文为了获取这些特征,引入如下定义.

图 1

Fig. 1

Fig. 1 Impact of frequency dynamic characteristics on network图 1 频谱的动态特征对网络的影响

定义4(地理连接). 一个地理连接当且仅当存在于认知用户SU_i和SU_j之间的距离小于r_s,例如:||X_i-X_j||<r_s.网络G(l_s,r_s)是没有考虑主网络影响的认知网络,因此,与传统的网络相同,它只包含地理连接.

定义5(频谱机会SOP(SU_i)). 被定义为在某些时段没有被授权用户占用、对认知用户可用的频段集合.

定义6(频谱连接). 当SU_i和SU_j有共同的可用信道时,频谱连接存在于它们之间.例如:

SOP(SU_i)ÇSOP(SU_j)¹Æ.

定义7(通信连接). 当且仅当SU_i和SU_j既有地理连接也有频谱连接时,通信连接才会存在.

因此,通信连接的存在是由节点间的距离和共同的可用频谱决定的.

当认知无线电网络中的可用频谱发生变化时,网络的传输时延也会发生相应的变化.因此,对该网络的时延分析需要首先对动态频谱环境进行建模.为此,本文提出了一个认知无线电图模型,将授权用户以及信道等影响因素进行一个逻辑划分.然后,在图模型上将认知用户的动态频谱接入过程建模为一个连续时间的马尔可夫链,从而可以获取用户的频谱接入概率.最后,建立认知用户的生存函数来量化这些因素的影响.

为了更直观地理解信道数量和授权用户的活动对网络时延的影响,本文引入了认知无线电图模型来拓展前面定义的网络模型G(l_s,r_s).

一般说来,信道越多,网络时延应该越低.既然两个节点间通信连接的存在性依赖于分配给地理连接的可用频段,那么认知无线电网络的时延就依赖于当前的可用频谱数量.用V代表节点的集合,E_k表示网络中相对于信道k的频谱连接,G_k代表节点在信道k上的图,则G_k=(V,E_k).一个连接l=(v_i,v_j)ÎE_k当且仅当v_i与v_j之间有地理连接,并且将信道k分配给该连接.按照地理连接和频谱连接的定义,图G(l_s,r_s)可以划分为物理拓扑和逻辑拓扑(如图 2所示).在逻辑拓扑上,每一层都是按照信道划分的一个子图,例如,在信道k上的子图可以表示为G_k,它表示网络在信道k上的连通状况.

图 2

Fig. 2

Fig. 2 Cognitive radio graph model图 2 认知无线电图模型

现在定义G=(V,E)作为本文的认知无线电图模型.其中,E代表所有可用的频谱连接,例如因此,G可以被视为一个多层图.假设图中所有的节点都具有相同的传输功率,则在每一子图上,网络的时延就主要受授权用户的活动影响.在图 2中,如果一个源节点S需要向目的节点D传送数据,首先,源节点使用信道f₁将数据传送至B节点;此后,授权用户占用信道f₁,节点B切换至信道f₂继续传输.当信道f₂上也出现授权用户后,中转节点需要继续寻找其他信道完成传输(图 2中又切换回f₁).

上述认知无线电图模型分析了授权用户的活动和信道数量对时延的影响.为了量化这些因素的影响,本文将认知用户的机会式频谱接入过程建模为一个连续时间的马尔可夫链.假设共有N个注册信道,每个授权用户可以使用一个信道进行通信.当授权用户到来时,它可以强占被认知用户使用的信道.在马尔可夫链中,模型的状态转换如图 3所示.该模型利用可用信道的数量i来表示每个状态,在某个时间t,状态空间S(t)可以表示为

S(t)={i|0≤i≤N,t≥0} (1)

图 3

Fig. 3

Fig. 3 Continuous-Time Markov chain model图 3 连续时间-马尔可夫链模型

授权用户的出现,被看作是一个到达率为g_p的泊松过程.授权用户的服务时间服从一个期望值为1/m_p的负指数分布.

将P_i(t)表示为iÎS(t)的稳态概率分布,它表示认知用户拥有i个可用信道的概率.状态i根据授权用户的到达和离开,可以被转换到下面状态的一种:当一个新的授权用户到达后,状态转换到i-1;当授权用户离开后,状态转换到i+1.通过解该模型,可以获得稳态分布概率.然后,就可以计算认知用户拥有通信连接的概率.本文将这个概率定义为认知用户的生存概率.该概率在认知无线电网络的时延分析中起着很重要的作用,我们将在下一节中重点加以阐述.

定义8(生存函数j(t)). 生存函数j(t)实际上充当了一个认知用户在某时刻t至少有一个通信连接的概率.通信连接是随着SOP的动态性和差异性而变化的.因此,j(t)与注册信道的数量和授权用户的活动都有关系.

假设认知节点SU₁与SU₂相邻,SU₁的可用信道数量为i,SU₂的可用信道数量为j,则SU₁与SU₂之间至少存在一条公共信道的概率为

(2)

将SU₁处于状态i时与其他邻居节点有公用信道的概率表示为Q_i(t),则Q_i(t)的计算如下:

(3)

因此,当知道了用户处于某个状态时的概率以及在该状态时与邻居节点的共享公用信道的概率后,就可以获取认知用户的生存函数:

(4)

综上所述,动态频谱环境下的认知无线电网络的每个用户都与一个生存函数j(t)有关.根据抽样定理^[18],生存用户的点过程是一个密度函数为l(t)=j(t)l_s的点过程,即:在某时刻t采样过的认知网络,本文将其表示为G(l_s,r_s,j(t)),该网络中的节点集合只包含G(l_s,r_s)中有通信连接的节点.因此,分析动态频谱环境下的认知无线电网络时延,只需要对网络G(l_s,r_s,j(t))进行分析.

下面将在上述网络G(l_s,r_s,j(t))的基础上,采用首次通过渗流理论对大规模认知无线电网络的时延进行分析.

本文首先将用户间的信息传输构建成几何随机图上的一个首次通过渗流过程^[18];然后,在该模型上分析认知无线电网络传输时延.由首次通过渗流过程获取的网络传输时延,可以看作是目的节点最先收到来自源节点消息的时间.在本文前期工作^[19]的定理1中已经证明:当授权用户密度大于关键密度,即时,网络G(l_s,r_s,j(t))内不存在无限连通分支,即,网络不连通的概率为1.这种情况下,网络时延趋于无穷大,对其进行分析没有实质意义.因此,本文只针对网络可能存在连通的情况(即)进行研究.另外,为了突出认知无线电网络中频谱的动态变化性对传输时延的影响,本文忽略了由于消息的竞争、排队等带来的传播时延.

假设网络G(l_s,r_s,j(t))极大连通分支的一个节点u在某时刻广播一个消息,如果网络G(l_s,r_s,j(t))处于连通状态,那么在忽略传输延时的情况下,G(l_s,r_s,j(t))的所有节点将立即接收到该消息;另一方面,如果网络G(l_s,r_s,j(t))处于次连通状态,几乎所有其他节点都无法立即接收到消息.尽管如此,由于频谱可用性的变化,经过若干时间之后,消息仍然可能被传输到G(l_s,r_s,j(t))连通分支之外的节点.首次通过渗流过程主要研究网络中任意目的节点最先收到来自u的消息的时间延迟,下面给出该过程的形式化描述.

用T(X_u,X_v)表示从节点u到节点v的最小传输时延,将i-1节点到达i节点的时间表示为一个随机变量T_i,则v首次接收到来自u的消息的传输时延可以表示为

(5)

其中,l(X_u,X_v)是从节点u到节点v的一条路径,L(X_u,X_v)是从节点u到节点v的所有路径的集合,V(l(X_u,X_v))是路径所经历的节点的集合.为了简化符号,本文在以下部分用T(u,v)来表示传输时延T(X_u,X_v).

定理1. 给定一个网络G(l_s,r_s,j(t)),且,则存在:

(1) 如果网络处于连通状态,则:

(6)

(2) 如果网络处于次连通状态,则存在:

(7)

使得:

(8)

其中,d(u,v)为节点u到v的物理距离,q(l_s,j(t))是与l_s和j(t)相关的常数,x为常数.

为证明以上结论,需要用到以下两个引理.

引理1(文献[20]中引理6). 给定一个网络G(l_s,r_s,j(t)),假设节点vÏC_max(G(l_s,r_s,j(t))),且,即,m是极大连通分支C_max中离节点v最近的一个节点,则d(m,v)<¥.

引理2. 给定一个处于关键密度的网络并且则从节点u到v传输所经历的最小跳数为那么,存在常数x,使得:

(9)

引理2可以采用Liggett提出的次加遍历性理论^[21]加以证明,在文献^[1]和文献^[6]中都有研究,受篇幅所限,这里不再详细论述.

下面证明定理1.

证明:

(1) 当网络G(l_s,r_s,j(t))处于连通状态时,网络中只存在一个极大连通分支.对于任意两个节点u和v,当d(u,v)®¥时,存在以下两种情况:① 两个节点都处于极大连通分支C_max(G(l_s,r_s,j(t)))(后面简称C_max(t))中,在这种情况下,T(u,v)=0;② 节点u和v中有至少一个节点不在C_max(t)中,假设在t₁时刻,C_max(t₁)中的节点可以第一时间收到来自u的信息,则能够在C_max(t₁)中找到分别距离u和v最近的两个节点m₁和m₂,分别表示如下:

(10)

由于节点m₁和m₂都位于极大连通分支中,则T(m₁,m₂)=0.因此可以得到:

(11)

令为u到m₁的最少跳数,T_i为每一跳的可用频谱等待时延.由引理1可知d(u,m₁)<¥,因此可以得到则同理,还可以得到E[T(m₁,v)]<¥.

综上,可以得到结论定理1的第1部分得证.

(2) 当网络G(l_s,r_s,j(t))处于次连通状态时,对于任意两个节点u和v,当d(u,v)®¥时,两个节点不可能处于同一个连通分支中,因此,T(u,v)>0.将节点u看作是原点,射线X_u,X_v看作是x轴.不失一般性,这里将认知节点的传输半径设为1,则离节点v的横坐标最近的整数可以记为k.因此,T(0,k)=T(X_u,X_v)且k-1≤d(u,v)≤k+1.如果X_v¹X_k,则T(0,k)=T(u,v),可以得到:

(12)

相反地,如果X_v¹X_n,则X_n必定与X_v相邻,则T(0,k)-T(X_k,X_v)≤T(u,v)≤T(0,k)+T(X_k,X_v),因此可以得到:

(13)

因此,根据次加遍历性理论^[21],存在0<q(l_s,j(t))<¥,使得:

(14)

下面论述如何通过计算来获取q(l_s,j(t))更为精确的上限值.

假设沿着从u到v的任意一条路径l的延时为T(l),则:

(15)

由公式(15)可以看出:要计算整条路径传输的时延,需要先计算出

根据抽样定理^[18],可以找到变化的节点密度与关键密度之间的关系.例如,假设当前节点密度满足,通过抽样可以降低节点密度至,该操作等同于将网络按比例缩小,节点u与节点v之间的距离就变成了.根据这一关系,可以将的计算转换为与有关的计算,而无需计算每种节点密度下的最小跳数.按照引理1,可以得到:

(16)

因此,

(17)

假设路径中每一跳的等待时延满足几何分布(这里忽略传输时延的影响),则:

Pr(T_i=k)=(1-j(t))^kj(t) (18)

可以得到的期望时延为

(19)

综合公式(5)、公式(17)与公式(19),可以得到.

因此,定理1的第2部分得证.

从以上结论可以看出,认知无线电网络延时/距离比与认知节点密度成反比:节点密度越大,网络时延相对也就越小,则比值越小.另外,延时/距离比与生存函数也成反比:生存函数的值越大,网络时延相对就越小,则比值也就越小.因此,网络设计者可以通过调整相关参数获得更好的网络性能.

本文仿真考虑一种洪泛的机制.在洪泛的过程中,每个接收到信息的节点都要转发给它的所有邻居,从源节点到目的节点间的所有路径都会进行信息传输.依据前面的时延分析模型,目的节点第1次接收到源节点信息的时间被看作是最短时延.该洪泛机制也适用于其他无线路由协议.本文通过追踪得到信息传播的最小时延后计算时延与节点间的物理距离的比值来观察网络时延的变化规律.

仿真实验在Matlab7.1的环境下进行:首先,在10x10的区域内部署160~350个节点,即,节点密度在1.6~3.5范围内变化;其次,区域内的每个节点依据自身生存函数与周围邻居建立连接;然后,在场景内随机生成不同的源节点和目的节点,进行数据传输并获取其传输时延;最后,利用获取的数据分别分析当节点密度l_s以及授权用户活动和信道数量变化时对时延/距离比q所产生的影响.根据本文第3节的动态频谱环境模型,授权用户活动和信道数量的影响又可以量化为生存函数j(t)的影响.因此,在以下分析中,本文主要考虑认知用户节点密度以及用户生存函数对时延/距离比的影响.

图 4展示的是生存函数值为0.4时,节点密度的变化对网络时延的影响.图 4(a)~图 4(c)分别是l_s=1.6,2.0,3.5的时延/距离比随端到端距离变化的分布情况.以图 4(a)为例,每个端到端时延/距离比在图中被显示为一个点.随着距离的增大,这些点被连成了不同的曲线.每条曲线上的点都具有相同的时延,而且曲线的颜色由浅到深分别表示时延/距离比的值由低到高变化.还可以注意到:图 4(a)中的时延/距离比最终趋近于一个大于0的常数,说明该网络时延与距离呈线性发生变化,处于次连通状态.这是由于,当j(t)=0.4时,节点的密度如果太小就无法构建一个连通网络.从图 4(b)可以看出:将节点用户密度增加到2.0后,时延/距离比最终趋近于一个更小的常数,网络连通状态有所改善,但仍不足以构建一个连通网络.图 4(c)中的节点密度增加到了3.5,时延/距离比趋近于0,此时网络处于连通状态.因此,该仿真结果与本文的定理1相符合.同时,根据其他文献对关键密度^[8]和时延/距离比^[15]的研究,分别取x≈0.79,还可以计算得到图 4(a)~图 4(c)中的时延/距离比的上限值分别为1.06,0.85,0.49.通过对比图 4中的时延/距离比,都小于各自相应的上限值,也符合定理1中关于时延/距离比的上限的约束.

图 4

Fig. 4

Fig. 4 Impact of node density on network latency图 4 节点密度对网络时延的影响

本组实验主要通过仿真生存函数j(t)对认知无线电网络时延/距离比的影响,来展现授权用户活动和信道数量的影响.图 5展示的是当节点密度l_s=1.9时,生存函数分别为j(t)=0.2,0.5,0.8的时延/距离比的变化情况.与图 4相近,图 5(a)和图 5(b)的时延/距离比也趋近于一个大于0的常数,网络时延与距离的变化呈线性关系.这说明,当l_s=1.9时,生存函数的值如果太小就会导致网络处于次连通状态.原因是,由于授权用户活动过于频繁或者可用信道数目太少导致的.当生存函数增加到0.8之后,时延/距离比趋近于0,网络处于连通状态.此时,该仿真结果也与本文的定理1相符合.同样,也可以算出图 5(a)~图 5(c)中的时延/距离比的上限值分别为2.4,0.6,0.15.通过对比图 5中的时延/距离比可以发现:它们都小于各自相应的上限值,符合定理1中关于时延/距离比的上限的约束.

图 5

Fig. 5

Fig. 5 Impact of survival function on network latency图 5 生存函数对网络时延的影响

目前,针对传统无线网络的时延分析没有考虑到频谱的动态变化性.因此,现有的分析方法不适用于认知无线电网络.本文通过构建动态频谱模型来分析和量化授权用户活动以及信道数量等因素对频谱环境造成的影响.然后,又结合首次通过渗流理论分析了不同连通状态下大规模认知无线电网络时延的伸缩规律,并给出了时延与距离比的上限值.仿真实验结果表明,频谱的动态性会对认知无线电网络时延产生极大的影响.

然而,本文提出的时延分析方法本质上都是理论分析,缺少在实际无线应用场景中的测试.如何基于真实无线信道模型搭建认知无线电平台,并将这些时延分析的结论应用到网络路由设计以及信息分发机制中去,让系统能够自适应地调整相关参数获得更好的网络性能,是我们下一步研究的重点.