面向物联网的机会网络信息传输最优控制策略

吴亚辉, 马武彬, 邓 苏, 周浩浩, 戴超凡

(国防科技大学信息系统工程重点实验室, 湖南 长沙 410073)

0 引 言

随着网络和传感器技术的迅猛发展,物联网[1]逐步为人所熟知并融入大众日常生活。2005年11月17日, 国际电信联盟(International Telecommunication union, ITU)发布了《ITU互联网报告2005:物联网》,正式提出了“物联网”的概念。所谓物联网,简单来说就是万物互联的意思,是在互联网的基础上所延伸出的新概念,其核心就是世界万物基于不同类型网络模式进行互联、互通和互操作,进而形成一个庞大的复杂系统。物联网一经提出就迅速引起世界各国研究人员与工业界的重视,目前已经在人们日常生活的方方面面得到了体现,如智能家居[2]、智慧交通[3]等。近期,随着元宇宙[4]概念的提出,物联网的价值将会进一步凸显。元宇宙通过融合多种前沿技术形成一个虚实相融的新型空间,其关键点是现实世界与虚拟世界的链接,而物联网是实现这一目标的重要支撑技术之一[5]。反过来,元宇宙也必然推动物联网组成单元向大规模发展,使得物联网系统更为复杂。物联网各组成要素互联互通的前提是保障各节点及时掌握相关信息,因此信息传输的可靠性非常关键。但在大规模物联网系统中,由于节点众多和泛在连接特性,为信息传输的可靠性带来极大挑战:一是大量移动节点导致网络拓扑时变性更强;二是节点的海量性为传统通信基础设施带来极大通信压力;三是随着物联网系统的逐步落地,其应用场景也更为多元化,如战场空间、抗震救灾等恶劣环境。此时,传统的通信基础设施更加不可控,信息传输中断的情况时有发生,进一步增加了问题的复杂性。为了在此环境下,提升信息传输效率,研究人员提出了机会网络[6]的概念,通过在传输层与应用层之间添加一层束层,实现存储-携带-转发的信息传输模式,尽可能克服网络中断与分割的问题。当前,已经有不少研究人员对机会网络在物联网领域的应用开展了探索[7-9],未来随着物联网规模及应用场景的复杂化,机会网络必然有着更为广阔的应用前景。

在机会网络存储-携带-转发的信息传输模式中,节点不需要像传统移动自组网路由策略那样维护到其他节点的路由信息,而只需要把需要传输的信息暂时存储在当前节点上,并且随着自身的移动而随身携带。一旦出现合适的通信机会,即进行信息复制或转发,从而实现信息的接力式传输。但在实际应用中,信息转发过程需要消耗一定能量,而物联网系统中存在大量的无线设备,其体积较小,能量容量有限。在此背景下,如果进行无限制的泛洪式的信息转发,必然会导致某些节点的能量迅速消耗。因此,如何兼顾能量消耗与信息传输效率是需要考虑的重要问题[10]。文献[11]综合考虑机会网络中节点之间的社会关系及能量消耗情况,来提升信息传输效率。文献[12]提出了基于Stackelberg博弈的信息传输策略,一方面降低了能量消耗,另一方面可以激励节点的广泛参与,进而实现在降低能量消耗的同时尽可能改善信息传输性能。文献[13]提出了基于多目标优化的信息传输算法,同步考虑了能量消耗、信息传输步长、节点距离、传输成功率4个目标。文献[14]则从信息价值的角度来降低信息传输过程的能量消耗,在一定程度上解决了传统基于网络结构设计的传输策略存在的部分节点能量急剧消耗的问题。文献[15]根据机会网络中节点的活跃度以及剩余能量,来设计信息传输策略,提升了能量消耗的均衡性。以上工作结合不同的场景设计了相应的传输算法,并通过大量仿真实验进行了验证。相对应的,也有一部分工作试图建立具有一定普适性的数学模型,来描述信息传输过程背后的理论规律,重点从理论上探索信息传输策略的最优性。文献[16]基于马尔可夫过程构建了泛洪策略(epidemic routing,ER)的信息传输模型,能够精准评估信息传输性能。文献[17]则建立了ER算法与节点密度之间的理论分析模型,从而能够根据节点密度对传输性能进行定量评估。为降低模型的状态空间,以上文献通过微分方程进行近似,进而提出了相应的微分模型(ordinary differential equations, ODE)。在ODE的基础上,文献[18]利用最优控制理论提出了带有能量约束的传输控制策略。文献[19]则针对机会网络节点稀疏的特点,提出了基于最优化理论的节点最优探测策略,从而降低探测过程的能量消耗。文献[20]考虑多播场景,提出了面向Two-hop算法的能量控制算法,进而可以有效利用有限的能量提升信息传输效率。本文主要考虑面向物联网的应用场景,结合其万物互联的基本需求,每一个节点都是潜在的信息需求节点。因此,本文同样采用多播场景,即同时存在多个目的节点,主要创新点归纳如下:

(1) 提出了面向多目的节点且带有传输不可靠性的性能评估模型。为克服Two-hop算法传播速度慢的问题,该模型采用概率ER传输算法,可通过控制传输概率,来平衡能量消耗及传输速率,提升传输效率。

(2) 基于庞特李雅金极大值定理[21],提出了最优传输策略(概率的最优取值),且从理论上证明了最优策略服从阈值形式。

(3) 通过仿真实验验证了传输模型的精确性,以及传输策略的有效性。

1 信息传输过程建模

1.1 系统模型

本文假设物联网节点共分为两大类:传输节点、目的节点。所谓传输节点是指对信息不感兴趣,但协助信息传递的节点;目的节点则是指对信息感兴趣的节点,即信息的需求方。同时,传输节点与目的节点是相对于具体的信息来说的,针对不同的信息,一个节点即可能是传输节点,也可能是目的节点。在存储-携带-转发的信息传输模式下,两个物联网节点只有移动到彼此的通信范围之内方可进行信息交互,因此节点移动特性十分重要。当前,大量文献对人类、车辆等的移动轨迹进行深入分析,发现其运动基本服从泊松模型,即两个节点相遇的时间间隔服从负指数分布[22-23]。而人、车辆等是物联网节点的重要组成部分。因此,本文同样采用泊松运动模型,且假设传输节点内部,以及传输节点与目的节点之间的相遇速率分别为α和β。此时,以传输节点为例,两个节点在时间区间Δt内相遇的概率为1-e-αΔt。传输节点与目的节点数目分别设定为N和M。在初始时刻0,只有一个传输节点携带信息,且需要在信息有效期内发送到尽可能多的目的节点。信息时效性设定为T。以X(t)代表在时刻t携带信息的传输节点数目,显然X(0)=1。类似地,以Y(t)代表在时刻t携带信息的目的节点数目,且满足Y(0)=0。另外,由于本文采用概率ER算法,以p(t)代表在时刻t一个传输节点向其他传输节点发送信息的概率。由于目的节点是信息的需求端,假设传输节点始终以概率1向其发送信息。简单起见,本文进一步假设目的节点具有一定自私性[23-26],内部不互相传输信息。实际上,本文所提出的模型在没有此假设时同样成立。另外,以q代表一次传输成功的概率,取值为(0, 1],用于描述传输过程中由于干扰等因素引起的不确定性。

1.2 信息传输评估模型

首先,对于变量X(t),其满足如下公式:

(1)

式(1)意味着在时刻t+Δt,携带信息的传输节点数只与上一个时刻t的状态有关,信息的传输过程服从马尔可夫分布。其中,Ω(t)代表在时刻t未携带信息的传输节点集合,ωj(t,t+Δt)代表节点j在时间区间[t,t+Δt]内获得信息的概率,可知:

ωj(t,t+Δt)=1-e-αΔtX(t)p(t)q

(2)

结合文献[16-17],可得

(3)

式中:E(·)代表随机变量*的期望值。显然,式(3)是对式(1)的近似,把马尔可夫过程利用平均场理论近似为微分方程,这也是当前复杂系统传播动力学中常用的方法[16-17]。通过这种转换一方面降低了状态空间,使得计算过程更为简单,更重要的是为后面利用极大值定理获取最优策略奠定了基础。此种转换的精确性将通过仿真实验进行验证。

类似地,对于随机变量Y(t),可以得到:

(4)

下面开始探讨信息传输过程中的能量消耗,按照文献[19-27],其与信息的传输次数成正比。但是,当前文献都假设每一次传输都是成功的,此时传输次数与获得信息的节点数一致。本文在传输过程考虑了不缺性,因此上述两个值并非一样的。为此,本文以F(t)代表到时刻t为止的传输总次数,可知F(0)=0,且满足:

(5)

本文的主要目标是提升能量使用效率,即在能量消耗与信息传输性能之间取得折中。以U(t)代表到时刻t的性能,则可得:

E(U(t))=E(Y(t))-δE(F(t))

(6)

式中:E(Y(T))代表获得信息的目的节点数;δ代表能量消耗权重因子,用于平衡传输效果与能量消耗占比。由于获得信息的目的节点数越多越好,因此E(Y(T))反映了正收益。E(F(T))代表总的信息传输次数。根据文献[19-27],信息传输能量消耗与传输次数成正比,本文以δE(Y(T))表示能量消耗,代表信息传输所引起的负收益。因此,式(6)代表了信息传输的最终性能。一般来说,δ取值大于0即可,代表信息传输过程消耗能量越多,总体性能下降。但在实际中,通常还要满足δ

(7)

其中,优化目标是获得最优的信息传输性能。在保障合理的能量消耗之时,让更多的目的节点获得信息。p(t)为模型中的控制变量,代表了传输节点在时刻t向其他节点发送信息的概率。在任意时刻t,p(t)的取值区间均为0到1。模型(7)的目标就是获取p(t)在任意时刻的最优取值,使得优化目标E(U(T))达到最大值。p(t)在时间区间[0,T]内任意时刻的最优值集合,即为最优控制策略p*。X(0)和Y(0)分别代表在初始时刻携带信息的传输节点和目的节点数。因此,X(0)=1,Y(0)=0表示在最初时刻,只有一个信息源,且所有目的节点均未获得信息。

根据式(6),可知:

(8)

如果q≤δ,则E(U(t))始终处于非递增状态,即效用值始终不会增加,此时传输节点没必要进行信息传输。因此,下面只考虑q>δ的情形。

2 最优传输策略

2.1 最优传输策略构建

首先,本文需要证明式(7)所示的优化问题存在解,且有定理1。

定理 1对于控制参数p,存在最优值p*,以及对应的状态变量X*、Y*,使得式(7)所示的优化问题达到最优。

证明首先,很容易验证以下3个条件:① 控制参数p(t)的取值范围为0到1,从整个信息的生命周期来看,p的取值为一个闭凸集合;② 式(3)～式(5)都是关于p的线性方程,且仅依赖于时间及状态变量;③ 式(7)中的优化函数为凸函数。此时,根据Filippov定理[28]即可知定理成立。

定理1仅仅给出了解的存在性,且最优解是一条随时间变化的曲线,属于典型的泛函极值问题。为获得最优解p*,本文还需要用到庞特里亚金极大值定理[21],从而构造处最优解的形式。

首先,基于式(7)的优化目标,以及式(3)～式(5),构建汉密尔顿方程如下:

(9)

基于式(9),可得伴随状态方程如下:

(10)

式中:λX和λY为伴随状态变量(也称为共态变量)。根据文献[21],其终端条件需满足如下条件:

λX(T)=λY(T)=0

(11)

根据庞特里亚金极大值定理[21],可以知道存在连续或分段连续的可微状态和伴随状态函数满足:

(12)

式(12)把式(7)所示的最优控制问题转化为使哈密顿函数H最大化的问题。同时,文献[21]中的庞特里亚金极大值定理,要求在每个时刻都要使得控制变量p(t)最大化汉密尔顿函数。因此,在任意给定时刻t,p(t)都要使得当前时刻的汉密尔顿函数H达到最大值。由于在任意给定时刻t,p(t)为唯一控制变量,因此可以认为其余参数都是已知的。基于上述分析,可知最优策略p*满足:

(13)

式(13)所示的最优解是一条随时间变化的曲线,代表了任意时刻t传输策略的取值。其中,∂H/∂p>0时,H随着p递增,p的最优取值为1;而∂H/∂p<0时,取值为0。同时,在∂H/∂p=0时,p可以在区间[0, 1]内取任意值。

证毕

2.2 最优传输策略结构

式(13)所示的最优传输策略满足定理2。

定理 2最优策略p*满足以下结构之一:①p(t)=1,0≤t≤T;②p(t)=0,0≤t≤T;③ 存在一个时刻s,p(t)=1,0≤t

证明首先,定义如下函数:

(14)

由于N-X和X均大于0(N=X时所有传输节点均已经获得信息,p=0),f可转换为函数g:

g=λXq-δ

(15)

假设存在一个时刻s,满足f(s)=g(s)=0,则进一步可知:

(16)

根据后面的定理3,可知函数(16)中(1+λY(s))q-δ>0。同时,由于q(-β(M-Y(s)))<0,可知式(16)在时刻s处的值小于0,即在时刻s,函数g为递减状态,显然下一时刻h满足g(h)<0,此时可得p(h)=0。进一步,可知式(16)在时刻h处同样小于0。因此,如果s存在,就有g(t)<0,s0。因此,函数g满足,g(t)>0,0≤t

从定理2可知,如果满足第1种情形,则发送概率一直为1,为典型的ER算法;如果满足第2种情况,则p一直为0,为典型的直接传输算法;在第3种情形下,p首先以概率1发送信息,到达给定时刻时,直接停止发送。因此,式(13)所示的最优策略具有简单的阈值结构,便于在实际场景种应用。

证毕

为支撑式(16)所示函数变化趋势的证明,从而验证定理2的准确性,下面提出定理3。

定理 3在任意时刻t,v(t)=(1+λY)q-δ>0。

证明首先,对函数v求导数可得

(17)

假设存在一个时刻s,v(s) ≤0。则可知从时刻s开始,v一直满足v≤0,即λY≤δ/q-1。由于q>δ,可知λY≤δ/q-1<0,进而可得λY(T)<0,这与式(11)所示的终端条件矛盾。显然假设不成立,v(t)始终大于0。

证毕

3 性能分析

首先,基于机会网络仿真平台[29]对模型的精确性进行验证。主要考虑3种常用的运动模型:泊松运动模型和两种实际运动轨迹。这几种模型分别模拟了车辆及人的运动规律,并已广泛运用于现有研究中。对于泊松运动模型,节点相遇服从负指数分布,传输节点与目的节点之间的相遇速率设置为3.71×10-6s-1,其值来源于上海出租车运动轨迹[22],假设包含100个传输节点及10个目的节点。传输节点内部相遇速率设置为2×3.71×10-6s-1。对于第1种模型,采用Infocom’05数据集[23],该数据集包含了41人的运动轨迹,首先统计节点相遇规律,并利用指数模型进行拟合,然后利用计算出的平均相遇时间间隔作为参数生成200个节点,包含150个传输节点及50个目的节点。第2种实际运动模型采用Cambridge数据集[30],共包含36个运动节点。采用同样的方式进行处理后,选择其中24个节点作为传输节点,其余12个节点为目的节点。

对于其余共同参数,基本设置如下:q=0.5,δ=0.01。考虑3种静态传输策略: ①p(t)=0, 0≤t≤T; ②p(t)=0.5, 0≤t≤T; ③p(t)=1, 0≤t≤T。每个场景运行50次仿真实验,计算平均值得到仿真结果,通过与计算结果对比,结果如图1所示。

图1 计算与仿真结果对比

从图1可以看出,该模型的计算结果与实际仿真结果之间的差异较小,3项实验的平均误差大约在4.08%以内。下面重点以泊松运动模型为例,分析本文得到的最优传输策略的性能。假设信息的有效期T为100 000 s,通过与前面3种静态策略相比,可以得到整个信息传输周期内的传输性能,如图2所示。

从图2可以看出,本文所提出的最优策略性能优于其他几个静态策略。同时,在中间时刻,本文所提出的策略的性能略低于静态策略(p=1)。实际上,p=1时为ER,信息传播速度最快,但其能量消耗巨大,导致在后面性能开始低于最优控制策略,也就是在信息的有效期内,其最终获得的性能低于本文所提出的最优控制策略。

图3展示了不同策略下的能量消耗对比。从图3中可以看出,p=0时,由于不主动传递信息,其能量消耗为0。同时,在初始时期,由于最优策略以概率1传输信息,能量消耗略高于第2种静态策略(p=0.5),但这种消耗是必须的,有利于提升信息传输性能。后续随着时间的递增,最优传输策略的优势逐步体现,能量消耗明显低于其他策略。

图3 不同传输策略的能量消耗对比

下面考虑信息的有效期T从0增加到200 000 s,结果如图4所示。

图4 不同时效性的传输策略性能对比

图4显示出在信息有效期不同的情况下,本文所提出的最优传输策略总能够获得最佳性能,特别是随着有效期的递增,性能表现更好。在最优控制策略中,时间阈值的分布如图5所示。

图5 不同时效性下最优策略的阈值分布

在时效性大于40 000 s时,最优策略的阈值开始下降。由于在最优策略中,只有在时间阈值之前以概率1传输信息。图5意味着,在信息有效期较大时,会较早地停止信息传播。这是因为,信息有效期长时,只要在前期传播足够多的副本,后期就有充足的时间,能够保障让更多目的节点获得信息。而在信息有效期小于40 000 s时,由于有效期短,需要尽可能在前期产生尽可能多的副本,因此阈值反而较大。图6展示了在T为100 000 s时的最优传输策略,直观展示出其服从定理2所示的阈值架构。

图6 最优传输策略(T=100 000 s)

4 结 论

本文利用机会网络的信息传输模式来应对高动态物联网中的信息交换需求,建立了基于ODE的信息传输性能评价模型。进一步,利用极大值定理得到了最优传输策略,证明了最优传输策略服从阈值形式。最后,通过一系列仿真实验验证了模型的精确性,总体来说本文所构建的ODE对信息传输过程的拟合精准度大于95%。同时,实验也验证了定理2所提出的阈值结构,且随着信息有效期的递增,阈值呈下降趋势,即信息主动传输的周期下降,但总体性能提升。这说明本文所提出的策略可以在降低能耗的情况下,获得更好的信息传输效果。