吳亞輝, 馬武彬, 鄧 蘇, 周浩浩, 戴超凡

(國防科技大學(xué)信息系統(tǒng)工程重點實驗室, 湖南 長沙 410073)

0 引 言

隨著網(wǎng)絡(luò)和傳感器技術(shù)的迅猛發(fā)展,物聯(lián)網(wǎng)[1]逐步為人所熟知并融入大眾日常生活。2005年11月17日, 國際電信聯(lián)盟(International Telecommunication union, ITU)發(fā)布了《ITU互聯(lián)網(wǎng)報告2005:物聯(lián)網(wǎng)》,正式提出了“物聯(lián)網(wǎng)”的概念。所謂物聯(lián)網(wǎng),簡單來說就是萬物互聯(lián)的意思,是在互聯(lián)網(wǎng)的基礎(chǔ)上所延伸出的新概念,其核心就是世界萬物基于不同類型網(wǎng)絡(luò)模式進行互聯(lián)、互通和互操作,進而形成一個龐大的復(fù)雜系統(tǒng)。物聯(lián)網(wǎng)一經(jīng)提出就迅速引起世界各國研究人員與工業(yè)界的重視,目前已經(jīng)在人們?nèi)粘Ｉ畹姆椒矫婷娴玫搅梭w現(xiàn),如智能家居[2]、智慧交通[3]等。近期,隨著元宇宙[4]概念的提出,物聯(lián)網(wǎng)的價值將會進一步凸顯。元宇宙通過融合多種前沿技術(shù)形成一個虛實相融的新型空間,其關(guān)鍵點是現(xiàn)實世界與虛擬世界的鏈接,而物聯(lián)網(wǎng)是實現(xiàn)這一目標(biāo)的重要支撐技術(shù)之一[5]。反過來,元宇宙也必然推動物聯(lián)網(wǎng)組成單元向大規(guī)模發(fā)展,使得物聯(lián)網(wǎng)系統(tǒng)更為復(fù)雜。物聯(lián)網(wǎng)各組成要素互聯(lián)互通的前提是保障各節(jié)點及時掌握相關(guān)信息,因此信息傳輸?shù)目煽啃苑浅ｊP(guān)鍵。但在大規(guī)模物聯(lián)網(wǎng)系統(tǒng)中,由于節(jié)點眾多和泛在連接特性,為信息傳輸?shù)目煽啃詭順O大挑戰(zhàn):一是大量移動節(jié)點導(dǎo)致網(wǎng)絡(luò)拓撲時變性更強;二是節(jié)點的海量性為傳統(tǒng)通信基礎(chǔ)設(shè)施帶來極大通信壓力;三是隨著物聯(lián)網(wǎng)系統(tǒng)的逐步落地,其應(yīng)用場景也更為多元化,如戰(zhàn)場空間、抗震救災(zāi)等惡劣環(huán)境。此時,傳統(tǒng)的通信基礎(chǔ)設(shè)施更加不可控,信息傳輸中斷的情況時有發(fā)生,進一步增加了問題的復(fù)雜性。為了在此環(huán)境下,提升信息傳輸效率,研究人員提出了機會網(wǎng)絡(luò)[6]的概念,通過在傳輸層與應(yīng)用層之間添加一層束層,實現(xiàn)存儲-攜帶-轉(zhuǎn)發(fā)的信息傳輸模式,盡可能克服網(wǎng)絡(luò)中斷與分割的問題。當(dāng)前,已經(jīng)有不少研究人員對機會網(wǎng)絡(luò)在物聯(lián)網(wǎng)領(lǐng)域的應(yīng)用開展了探索[7-9],未來隨著物聯(lián)網(wǎng)規(guī)模及應(yīng)用場景的復(fù)雜化,機會網(wǎng)絡(luò)必然有著更為廣闊的應(yīng)用前景。

在機會網(wǎng)絡(luò)存儲-攜帶-轉(zhuǎn)發(fā)的信息傳輸模式中,節(jié)點不需要像傳統(tǒng)移動自組網(wǎng)路由策略那樣維護到其他節(jié)點的路由信息,而只需要把需要傳輸?shù)男畔簳r存儲在當(dāng)前節(jié)點上,并且隨著自身的移動而隨身攜帶。一旦出現(xiàn)合適的通信機會,即進行信息復(fù)制或轉(zhuǎn)發(fā),從而實現(xiàn)信息的接力式傳輸。但在實際應(yīng)用中,信息轉(zhuǎn)發(fā)過程需要消耗一定能量,而物聯(lián)網(wǎng)系統(tǒng)中存在大量的無線設(shè)備,其體積較小,能量容量有限。在此背景下,如果進行無限制的泛洪式的信息轉(zhuǎn)發(fā),必然會導(dǎo)致某些節(jié)點的能量迅速消耗。因此,如何兼顧能量消耗與信息傳輸效率是需要考慮的重要問題[10]。文獻[11]綜合考慮機會網(wǎng)絡(luò)中節(jié)點之間的社會關(guān)系及能量消耗情況,來提升信息傳輸效率。文獻[12]提出了基于Stackelberg博弈的信息傳輸策略,一方面降低了能量消耗,另一方面可以激勵節(jié)點的廣泛參與,進而實現(xiàn)在降低能量消耗的同時盡可能改善信息傳輸性能。文獻[13]提出了基于多目標(biāo)優(yōu)化的信息傳輸算法,同步考慮了能量消耗、信息傳輸步長、節(jié)點距離、傳輸成功率4個目標(biāo)。文獻[14]則從信息價值的角度來降低信息傳輸過程的能量消耗,在一定程度上解決了傳統(tǒng)基于網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計的傳輸策略存在的部分節(jié)點能量急劇消耗的問題。文獻[15]根據(jù)機會網(wǎng)絡(luò)中節(jié)點的活躍度以及剩余能量,來設(shè)計信息傳輸策略,提升了能量消耗的均衡性。以上工作結(jié)合不同的場景設(shè)計了相應(yīng)的傳輸算法,并通過大量仿真實驗進行了驗證。相對應(yīng)的,也有一部分工作試圖建立具有一定普適性的數(shù)學(xué)模型,來描述信息傳輸過程背后的理論規(guī)律,重點從理論上探索信息傳輸策略的最優(yōu)性。文獻[16]基于馬爾可夫過程構(gòu)建了泛洪策略(epidemic routing,ER)的信息傳輸模型,能夠精準(zhǔn)評估信息傳輸性能。文獻[17]則建立了ER算法與節(jié)點密度之間的理論分析模型,從而能夠根據(jù)節(jié)點密度對傳輸性能進行定量評估。為降低模型的狀態(tài)空間,以上文獻通過微分方程進行近似,進而提出了相應(yīng)的微分模型(ordinary differential equations, ODE)。在ODE的基礎(chǔ)上,文獻[18]利用最優(yōu)控制理論提出了帶有能量約束的傳輸控制策略。文獻[19]則針對機會網(wǎng)絡(luò)節(jié)點稀疏的特點,提出了基于最優(yōu)化理論的節(jié)點最優(yōu)探測策略,從而降低探測過程的能量消耗。文獻[20]考慮多播場景,提出了面向Two-hop算法的能量控制算法,進而可以有效利用有限的能量提升信息傳輸效率。本文主要考慮面向物聯(lián)網(wǎng)的應(yīng)用場景,結(jié)合其萬物互聯(lián)的基本需求,每一個節(jié)點都是潛在的信息需求節(jié)點。因此,本文同樣采用多播場景,即同時存在多個目的節(jié)點,主要創(chuàng)新點歸納如下:

(1) 提出了面向多目的節(jié)點且?guī)в袀鬏敳豢煽啃缘男阅茉u估模型。為克服Two-hop算法傳播速度慢的問題,該模型采用概率ER傳輸算法,可通過控制傳輸概率,來平衡能量消耗及傳輸速率,提升傳輸效率。

(2) 基于龐特李雅金極大值定理[21],提出了最優(yōu)傳輸策略(概率的最優(yōu)取值),且從理論上證明了最優(yōu)策略服從閾值形式。

(3) 通過仿真實驗驗證了傳輸模型的精確性,以及傳輸策略的有效性。

1 信息傳輸過程建模

1.1 系統(tǒng)模型

本文假設(shè)物聯(lián)網(wǎng)節(jié)點共分為兩大類:傳輸節(jié)點、目的節(jié)點。所謂傳輸節(jié)點是指對信息不感興趣,但協(xié)助信息傳遞的節(jié)點;目的節(jié)點則是指對信息感興趣的節(jié)點,即信息的需求方。同時,傳輸節(jié)點與目的節(jié)點是相對于具體的信息來說的,針對不同的信息,一個節(jié)點即可能是傳輸節(jié)點,也可能是目的節(jié)點。在存儲-攜帶-轉(zhuǎn)發(fā)的信息傳輸模式下,兩個物聯(lián)網(wǎng)節(jié)點只有移動到彼此的通信范圍之內(nèi)方可進行信息交互,因此節(jié)點移動特性十分重要。當(dāng)前,大量文獻對人類、車輛等的移動軌跡進行深入分析,發(fā)現(xiàn)其運動基本服從泊松模型,即兩個節(jié)點相遇的時間間隔服從負指數(shù)分布[22-23]。而人、車輛等是物聯(lián)網(wǎng)節(jié)點的重要組成部分。因此,本文同樣采用泊松運動模型,且假設(shè)傳輸節(jié)點內(nèi)部,以及傳輸節(jié)點與目的節(jié)點之間的相遇速率分別為α和β。此時,以傳輸節(jié)點為例,兩個節(jié)點在時間區(qū)間Δt內(nèi)相遇的概率為1-e-αΔt。傳輸節(jié)點與目的節(jié)點數(shù)目分別設(shè)定為N和M。在初始時刻0,只有一個傳輸節(jié)點攜帶信息,且需要在信息有效期內(nèi)發(fā)送到盡可能多的目的節(jié)點。信息時效性設(shè)定為T。以X(t)代表在時刻t攜帶信息的傳輸節(jié)點數(shù)目,顯然X(0)=1。類似地,以Y(t)代表在時刻t攜帶信息的目的節(jié)點數(shù)目,且滿足Y(0)=0。另外,由于本文采用概率ER算法,以p(t)代表在時刻t一個傳輸節(jié)點向其他傳輸節(jié)點發(fā)送信息的概率。由于目的節(jié)點是信息的需求端,假設(shè)傳輸節(jié)點始終以概率1向其發(fā)送信息。簡單起見,本文進一步假設(shè)目的節(jié)點具有一定自私性[23-26],內(nèi)部不互相傳輸信息。實際上,本文所提出的模型在沒有此假設(shè)時同樣成立。另外,以q代表一次傳輸成功的概率,取值為(0, 1],用于描述傳輸過程中由于干擾等因素引起的不確定性。

1.2 信息傳輸評估模型

首先,對于變量X(t),其滿足如下公式:

(1)

式(1)意味著在時刻t+Δt,攜帶信息的傳輸節(jié)點數(shù)只與上一個時刻t的狀態(tài)有關(guān),信息的傳輸過程服從馬爾可夫分布。其中,Ω(t)代表在時刻t未攜帶信息的傳輸節(jié)點集合,ωj(t,t+Δt)代表節(jié)點j在時間區(qū)間[t,t+Δt]內(nèi)獲得信息的概率,可知:

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

(2)

結(jié)合文獻[16-17],可得

(3)

式中:E(·)代表隨機變量*的期望值。顯然,式(3)是對式(1)的近似,把馬爾可夫過程利用平均場理論近似為微分方程,這也是當(dāng)前復(fù)雜系統(tǒng)傳播動力學(xué)中常用的方法[16-17]。通過這種轉(zhuǎn)換一方面降低了狀態(tài)空間,使得計算過程更為簡單,更重要的是為后面利用極大值定理獲取最優(yōu)策略奠定了基礎(chǔ)。此種轉(zhuǎn)換的精確性將通過仿真實驗進行驗證。

類似地,對于隨機變量Y(t),可以得到:

(4)

下面開始探討信息傳輸過程中的能量消耗,按照文獻[19-27],其與信息的傳輸次數(shù)成正比。但是,當(dāng)前文獻都假設(shè)每一次傳輸都是成功的,此時傳輸次數(shù)與獲得信息的節(jié)點數(shù)一致。本文在傳輸過程考慮了不缺性,因此上述兩個值并非一樣的。為此,本文以F(t)代表到時刻t為止的傳輸總次數(shù),可知F(0)=0,且滿足:

(5)

本文的主要目標(biāo)是提升能量使用效率,即在能量消耗與信息傳輸性能之間取得折中。以U(t)代表到時刻t的性能,則可得:

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

(6)

式中:E(Y(T))代表獲得信息的目的節(jié)點數(shù);δ代表能量消耗權(quán)重因子,用于平衡傳輸效果與能量消耗占比。由于獲得信息的目的節(jié)點數(shù)越多越好,因此E(Y(T))反映了正收益。E(F(T))代表總的信息傳輸次數(shù)。根據(jù)文獻[19-27],信息傳輸能量消耗與傳輸次數(shù)成正比,本文以δE(Y(T))表示能量消耗,代表信息傳輸所引起的負收益。因此,式(6)代表了信息傳輸?shù)淖罱K性能。一般來說,δ取值大于0即可,代表信息傳輸過程消耗能量越多,總體性能下降。但在實際中,通常還要滿足δ

(7)

其中,優(yōu)化目標(biāo)是獲得最優(yōu)的信息傳輸性能。在保障合理的能量消耗之時,讓更多的目的節(jié)點獲得信息。p(t)為模型中的控制變量,代表了傳輸節(jié)點在時刻t向其他節(jié)點發(fā)送信息的概率。在任意時刻t,p(t)的取值區(qū)間均為0到1。模型(7)的目標(biāo)就是獲取p(t)在任意時刻的最優(yōu)取值,使得優(yōu)化目標(biāo)E(U(T))達到最大值。p(t)在時間區(qū)間[0,T]內(nèi)任意時刻的最優(yōu)值集合,即為最優(yōu)控制策略p*。X(0)和Y(0)分別代表在初始時刻攜帶信息的傳輸節(jié)點和目的節(jié)點數(shù)。因此,X(0)=1,Y(0)=0表示在最初時刻,只有一個信息源,且所有目的節(jié)點均未獲得信息。

根據(jù)式(6),可知:

(8)

如果q≤δ,則E(U(t))始終處于非遞增狀態(tài),即效用值始終不會增加,此時傳輸節(jié)點沒必要進行信息傳輸。因此,下面只考慮q>δ的情形。

2 最優(yōu)傳輸策略

2.1 最優(yōu)傳輸策略構(gòu)建

首先,本文需要證明式(7)所示的優(yōu)化問題存在解,且有定理1。

定理 1對于控制參數(shù)p,存在最優(yōu)值p*,以及對應(yīng)的狀態(tài)變量X*、Y*,使得式(7)所示的優(yōu)化問題達到最優(yōu)。

證明首先,很容易驗證以下3個條件:① 控制參數(shù)p(t)的取值范圍為0到1,從整個信息的生命周期來看,p的取值為一個閉凸集合;② 式(3)～式(5)都是關(guān)于p的線性方程,且僅依賴于時間及狀態(tài)變量;③ 式(7)中的優(yōu)化函數(shù)為凸函數(shù)。此時,根據(jù)Filippov定理[28]即可知定理成立。

定理1僅僅給出了解的存在性,且最優(yōu)解是一條隨時間變化的曲線,屬于典型的泛函極值問題。為獲得最優(yōu)解p*,本文還需要用到龐特里亞金極大值定理[21],從而構(gòu)造處最優(yōu)解的形式。

首先,基于式(7)的優(yōu)化目標(biāo),以及式(3)～式(5),構(gòu)建漢密爾頓方程如下:

(9)

基于式(9),可得伴隨狀態(tài)方程如下:

(10)

式中:λX和λY為伴隨狀態(tài)變量(也稱為共態(tài)變量)。根據(jù)文獻[21],其終端條件需滿足如下條件:

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

(11)

根據(jù)龐特里亞金極大值定理[21],可以知道存在連續(xù)或分段連續(xù)的可微狀態(tài)和伴隨狀態(tài)函數(shù)滿足:

(12)

式(12)把式(7)所示的最優(yōu)控制問題轉(zhuǎn)化為使哈密頓函數(shù)H最大化的問題。同時,文獻[21]中的龐特里亞金極大值定理,要求在每個時刻都要使得控制變量p(t)最大化漢密爾頓函數(shù)。因此,在任意給定時刻t,p(t)都要使得當(dāng)前時刻的漢密爾頓函數(shù)H達到最大值。由于在任意給定時刻t,p(t)為唯一控制變量,因此可以認為其余參數(shù)都是已知的?；谏鲜龇治?可知最優(yōu)策略p*滿足:

(13)

式(13)所示的最優(yōu)解是一條隨時間變化的曲線,代表了任意時刻t傳輸策略的取值。其中,?H/?p>0時,H隨著p遞增,p的最優(yōu)取值為1;而?H/?p<0時,取值為0。同時,在?H/?p=0時,p可以在區(qū)間[0, 1]內(nèi)取任意值。

證畢

2.2 最優(yōu)傳輸策略結(jié)構(gòu)

式(13)所示的最優(yōu)傳輸策略滿足定理2。

定理 2最優(yōu)策略p*滿足以下結(jié)構(gòu)之一:①p(t)=1,0≤t≤T;②p(t)=0,0≤t≤T;③ 存在一個時刻s,p(t)=1,0≤t

證明首先,定義如下函數(shù):

(14)

由于N-X和X均大于0(N=X時所有傳輸節(jié)點均已經(jīng)獲得信息,p=0),f可轉(zhuǎn)換為函數(shù)g:

g=λXq-δ

(15)

假設(shè)存在一個時刻s,滿足f(s)=g(s)=0,則進一步可知:

(16)

根據(jù)后面的定理3,可知函數(shù)(16)中(1+λY(s))q-δ>0。同時,由于q(-β(M-Y(s)))<0,可知式(16)在時刻s處的值小于0,即在時刻s,函數(shù)g為遞減狀態(tài),顯然下一時刻h滿足g(h)<0,此時可得p(h)=0。進一步,可知式(16)在時刻h處同樣小于0。因此,如果s存在,就有g(shù)(t)<0,s0。因此,函數(shù)g滿足,g(t)>0,0≤t

從定理2可知,如果滿足第1種情形,則發(fā)送概率一直為1,為典型的ER算法;如果滿足第2種情況,則p一直為0,為典型的直接傳輸算法;在第3種情形下,p首先以概率1發(fā)送信息,到達給定時刻時,直接停止發(fā)送。因此,式(13)所示的最優(yōu)策略具有簡單的閾值結(jié)構(gòu),便于在實際場景種應(yīng)用。

證畢

為支撐式(16)所示函數(shù)變化趨勢的證明,從而驗證定理2的準(zhǔn)確性,下面提出定理3。

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

證明首先,對函數(shù)v求導(dǎo)數(shù)可得

(17)

假設(shè)存在一個時刻s,v(s) ≤0。則可知從時刻s開始,v一直滿足v≤0,即λY≤δ/q-1。由于q>δ,可知λY≤δ/q-1<0,進而可得λY(T)<0,這與式(11)所示的終端條件矛盾。顯然假設(shè)不成立,v(t)始終大于0。

證畢

3 性能分析

首先,基于機會網(wǎng)絡(luò)仿真平臺[29]對模型的精確性進行驗證。主要考慮3種常用的運動模型:泊松運動模型和兩種實際運動軌跡。這幾種模型分別模擬了車輛及人的運動規(guī)律,并已廣泛運用于現(xiàn)有研究中。對于泊松運動模型,節(jié)點相遇服從負指數(shù)分布,傳輸節(jié)點與目的節(jié)點之間的相遇速率設(shè)置為3.71×10-6s-1,其值來源于上海出租車運動軌跡[22],假設(shè)包含100個傳輸節(jié)點及10個目的節(jié)點。傳輸節(jié)點內(nèi)部相遇速率設(shè)置為2×3.71×10-6s-1。對于第1種模型,采用Infocom’05數(shù)據(jù)集[23],該數(shù)據(jù)集包含了41人的運動軌跡,首先統(tǒng)計節(jié)點相遇規(guī)律,并利用指數(shù)模型進行擬合,然后利用計算出的平均相遇時間間隔作為參數(shù)生成200個節(jié)點,包含150個傳輸節(jié)點及50個目的節(jié)點。第2種實際運動模型采用Cambridge數(shù)據(jù)集[30],共包含36個運動節(jié)點。采用同樣的方式進行處理后,選擇其中24個節(jié)點作為傳輸節(jié)點,其余12個節(jié)點為目的節(jié)點。

對于其余共同參數(shù),基本設(shè)置如下:q=0.5,δ=0.01。考慮3種靜態(tài)傳輸策略: ①p(t)=0, 0≤t≤T; ②p(t)=0.5, 0≤t≤T; ③p(t)=1, 0≤t≤T。每個場景運行50次仿真實驗,計算平均值得到仿真結(jié)果,通過與計算結(jié)果對比,結(jié)果如圖1所示。

圖1 計算與仿真結(jié)果對比

從圖1可以看出,該模型的計算結(jié)果與實際仿真結(jié)果之間的差異較小,3項實驗的平均誤差大約在4.08%以內(nèi)。下面重點以泊松運動模型為例,分析本文得到的最優(yōu)傳輸策略的性能。假設(shè)信息的有效期T為100 000 s,通過與前面3種靜態(tài)策略相比,可以得到整個信息傳輸周期內(nèi)的傳輸性能,如圖2所示。

從圖2可以看出,本文所提出的最優(yōu)策略性能優(yōu)于其他幾個靜態(tài)策略。同時,在中間時刻,本文所提出的策略的性能略低于靜態(tài)策略(p=1)。實際上,p=1時為ER,信息傳播速度最快,但其能量消耗巨大,導(dǎo)致在后面性能開始低于最優(yōu)控制策略,也就是在信息的有效期內(nèi),其最終獲得的性能低于本文所提出的最優(yōu)控制策略。

圖3展示了不同策略下的能量消耗對比。從圖3中可以看出,p=0時,由于不主動傳遞信息,其能量消耗為0。同時,在初始時期,由于最優(yōu)策略以概率1傳輸信息,能量消耗略高于第2種靜態(tài)策略(p=0.5),但這種消耗是必須的,有利于提升信息傳輸性能。后續(xù)隨著時間的遞增,最優(yōu)傳輸策略的優(yōu)勢逐步體現(xiàn),能量消耗明顯低于其他策略。

圖3 不同傳輸策略的能量消耗對比

下面考慮信息的有效期T從0增加到200 000 s,結(jié)果如圖4所示。

圖4 不同時效性的傳輸策略性能對比

圖4顯示出在信息有效期不同的情況下,本文所提出的最優(yōu)傳輸策略總能夠獲得最佳性能,特別是隨著有效期的遞增,性能表現(xiàn)更好。在最優(yōu)控制策略中,時間閾值的分布如圖5所示。

圖5 不同時效性下最優(yōu)策略的閾值分布

在時效性大于40 000 s時,最優(yōu)策略的閾值開始下降。由于在最優(yōu)策略中,只有在時間閾值之前以概率1傳輸信息。圖5意味著,在信息有效期較大時,會較早地停止信息傳播。這是因為,信息有效期長時,只要在前期傳播足夠多的副本,后期就有充足的時間,能夠保障讓更多目的節(jié)點獲得信息。而在信息有效期小于40 000 s時,由于有效期短,需要盡可能在前期產(chǎn)生盡可能多的副本,因此閾值反而較大。圖6展示了在T為100 000 s時的最優(yōu)傳輸策略,直觀展示出其服從定理2所示的閾值架構(gòu)。

圖6 最優(yōu)傳輸策略(T=100 000 s)

4 結(jié) 論

本文利用機會網(wǎng)絡(luò)的信息傳輸模式來應(yīng)對高動態(tài)物聯(lián)網(wǎng)中的信息交換需求,建立了基于ODE的信息傳輸性能評價模型。進一步,利用極大值定理得到了最優(yōu)傳輸策略,證明了最優(yōu)傳輸策略服從閾值形式。最后,通過一系列仿真實驗驗證了模型的精確性,總體來說本文所構(gòu)建的ODE對信息傳輸過程的擬合精準(zhǔn)度大于95%。同時,實驗也驗證了定理2所提出的閾值結(jié)構(gòu),且隨著信息有效期的遞增,閾值呈下降趨勢,即信息主動傳輸?shù)闹芷谙陆?但總體性能提升。這說明本文所提出的策略可以在降低能耗的情況下,獲得更好的信息傳輸效果。