面向物聯網的機會網絡信息傳輸最優控制策略

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

(國防科技大學信息系統工程重點實驗室, 湖南 長沙 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所提出的閾值結構,且隨著信息有效期的遞增,閾值呈下降趨勢,即信息主動傳輸的周期下降,但總體性能提升。這說明本文所提出的策略可以在降低能耗的情況下,獲得更好的信息傳輸效果。