胡宗升,邢 凱,2,許 靜
(1.中國科學技術大學 計算機科學與技術學院,合肥 230026;2.中國科學技術大學 蘇州高等研究院,江蘇 蘇州 215123)
無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)一般由一系列能夠感知周圍環(huán)境,使用無線信道進行通信的傳感器節(jié)點組成,是一種能夠進行感知、處理、存儲和傳輸感知區(qū)域信息的分布式自組織網(wǎng)絡,其在國防軍事、防災預警、氣候監(jiān)測、交通運輸、環(huán)境與農(nóng)業(yè)等領域具有廣泛的應用。在這些領域中,存在大量應用需要WSN 能夠快速、持續(xù)地收集全局信息,并及時做出決策和調度。因此,信息的收集匯聚是無線傳感器網(wǎng)絡的主要任務之一。但是,在數(shù)據(jù)多跳匯聚過程中,中繼節(jié)點的存儲轉發(fā)產(chǎn)生了大量的通信、存儲和能量開銷。而無線傳感節(jié)點只有有限的通信帶寬、存儲容量以及能量。在大規(guī)模分布式環(huán)境下,傳統(tǒng)方法難以調和其信息通信、存儲、能量約束與全局信息收集的持續(xù)性和及時性要求之間的沖突。為解決這一挑戰(zhàn),研究人員針對大規(guī)模分布式無線傳感器網(wǎng)絡在信息收集匯聚方面的傳輸和能耗問題進行了大量研究[1-3]。
在信息收集匯聚任務中,無線傳感器網(wǎng)絡一般通過網(wǎng)絡的各個節(jié)點將其所感知信息經(jīng)由中間節(jié)點多跳傳輸匯總到基站。這種方式的缺點主要是:依賴中間節(jié)點的路由中繼,如果中間節(jié)點故障,則會導致某些節(jié)點信息無法到達Sink 節(jié)點,繼而無法到達基站,因此需要常態(tài)化地、持續(xù)地監(jiān)控并維護網(wǎng)絡,開銷巨大;受限于單點失效問題,一旦匯聚節(jié)點失效,就意味著網(wǎng)絡可用性降低甚至不可用,對匯聚節(jié)點選取要求高;通信和能耗問題,節(jié)點離基站越近,通過該節(jié)點的信息越密集,中繼通信負載越大,能耗也越高,會帶來較嚴重的負載均衡問題,當基站附近的節(jié)點在耗盡能量、通信帶寬和存儲空間后,會導致可用性問題。
針對無線傳感器網(wǎng)絡在信息匯聚任務中的匯聚節(jié)點失效和中繼路由可靠性問題,當前研究往往采用骨干拓撲的方式,利用簇(如LEACH[4-5]算法)或者樹的方式(如LPT[6]算法)匯集數(shù)據(jù),例如網(wǎng)絡根據(jù)拓撲位置或能量等特性將網(wǎng)絡劃分為多個簇,或通過分布式匯聚算法形成樹狀等骨干拓撲,節(jié)點收集信息后發(fā)送給骨干拓撲節(jié)點并通過骨干網(wǎng)匯集信息。這種方式不依賴于中心節(jié)點,傳感器節(jié)點只需和附近鄰居節(jié)點通信,以自組織骨干網(wǎng)通過多跳的方式協(xié)作進行信息傳輸。相應地,節(jié)點也需要更多通信開銷來完成骨干網(wǎng)拓撲維護、時間同步、節(jié)點選舉等工作,從而導致較高的網(wǎng)絡延遲和維護開銷,因此對于全局信息收集有實時性要求的場景,例如防災預警、入侵檢測等難以提供有效保障,同時每個節(jié)點都有持續(xù)的通信和維護開銷,進一步擠壓了節(jié)點的通信和續(xù)航能力。然而,隨著對掌握全局信息需求的提高,傳統(tǒng)的信息匯聚方法不可避免地帶來全網(wǎng)范圍的信息收集和大量的中繼存儲轉發(fā)開銷,這些通信和存儲所帶來的能耗、帶寬及存儲開銷巨大。因此,如何降低網(wǎng)絡中的傳輸/存儲開銷一直是大規(guī)模分布式無線傳感器網(wǎng)絡信息收集與匯聚研究中的重點方向。
針對無線傳感器網(wǎng)絡在信息匯聚任務中的海量信息傳輸/存儲開銷問題,一個直觀的做法是將數(shù)據(jù)進行編碼/壓縮之后再進行傳輸和存儲。如面向多播傳輸?shù)木W(wǎng)絡編碼方法[7-9],基于圖論中最大流最小割原理保證了多播網(wǎng)絡在確定性路徑下可以達到網(wǎng)絡最大信息流,直觀上減少了網(wǎng)絡傳輸次數(shù),然而該方法在信息匯聚和單播網(wǎng)絡通信應用中因拓撲/路由的不確定性而難以被廣泛應用。壓縮感知[10](Compressor Sensing,CS)方法突破了傳統(tǒng)奈奎斯特采樣定理。不同于傳統(tǒng)的壓縮方法是先采樣再壓縮,壓縮感知則是采樣與壓縮同時進行,且解碼算法獨立于壓縮算法,因此尤其適合資源受限的傳感器網(wǎng)絡,壓縮和恢復算法的獨立意味著能夠根據(jù)傳輸路徑的變化而靈活地進行感知和數(shù)據(jù)重建。但是,壓縮感知是有損壓縮,其精度依賴于感知數(shù)據(jù)分布,當數(shù)據(jù)分布變化時穩(wěn)定性欠佳,在信噪比較低和分布波動大時尤其如此。不難看出,信息收集匯聚過程中的信息壓縮效率和相關算法的通用性始終是該研究領域的重要挑戰(zhàn)。
從以上研究進展可以看出,以計算開銷來降低/部分替代通信和存儲帶來的開銷,是資源受限的大規(guī)模分布式無線傳感器網(wǎng)絡的信息通信、存儲和能量約束與全局信息收集的持續(xù)性和及時性要求之間矛盾的一個重要趨勢變化,也是當前大規(guī)模分布式無線傳感器網(wǎng)絡研究的重點,即存算通信一體化研究。
針對大規(guī)模分布式無線傳感器網(wǎng)絡中以存儲轉發(fā)方式為主的傳統(tǒng)信息收集匯聚方式,本文提出一種以計算方式降低/部分替代通信和存儲開銷的存算通信一體化新方法,并給出相關理論分析和論證。
對信息的收集和匯聚是信息系統(tǒng)持續(xù)優(yōu)化和決策的前提條件,其中網(wǎng)絡拓撲的感知與維護在信息匯聚過程中不可缺少。
拓撲感知(Topology Sensing)是分布式網(wǎng)絡感知和維護拓撲信息的重要方法。Topology Sensing可以分為In-network 和Out-network 兩類。早期的拓撲感知的工作主要集中在網(wǎng)絡感知方面,并通過交換路由信息來實現(xiàn)。例如使用SNMP 協(xié)議主動監(jiān)測網(wǎng)絡中協(xié)議、接口、速度等信息來生成完整的網(wǎng)絡視覺地圖。也有研究利用開放最短路徑OSPF 來跟蹤域內(nèi)拓撲信息,以此來構建一個及時準確的拓撲信息。Out-network 受到了更廣泛的關注,文獻[11]將信息傳遞過程視作一個Hawkes 過程,從有限的被動網(wǎng)絡活動觀測來表征和分析無線網(wǎng)絡,檢測現(xiàn)有拓撲的變化以及提取網(wǎng)絡中信息流的信息,并利用模型和數(shù)據(jù)推斷網(wǎng)絡事件之間的聯(lián)系,識別出事件鏈。文獻[12]考慮WSN 中負載不均勻的問題,利用勢博弈理論,提出了拓撲控制算法BLTC。該算法能夠評估附近節(jié)點,根據(jù)效用函數(shù)選擇節(jié)點構建拓撲,將節(jié)點能耗均勻問題轉換為博弈問題,能夠有效提高網(wǎng)絡壽命,但缺點是網(wǎng)絡的博弈階段較長,延長了數(shù)據(jù)收集過程的延遲。文獻[13]進一步對網(wǎng)絡拓撲修復進行了調研,總結和分析了各類拓撲修復方法的優(yōu)缺點。
無線傳感器被大量應用于監(jiān)測預警的場景,如何保證這些場景下信息收集的準確性、實時性以及持續(xù)性是非常關鍵的問題。事件檢測的相關工作有基于閾值的方法、基于模式的方法和基于學習的方法[14]。在基于閾值的網(wǎng)絡監(jiān)測/事件檢測研究中,閾值通常由領域專家定義,當檢測到的值高于(低于)閾值時,會觸發(fā)通知事件,并通過網(wǎng)絡傳輸?shù)交净蛲獠肯到y(tǒng),其優(yōu)點是簡單,缺點是當數(shù)據(jù)需要傳輸?shù)较到y(tǒng)外部進行檢測評估時,增加了通信開銷,降低了事件檢測及時性。文獻[15]基于模式匹配的監(jiān)測方法從感知數(shù)據(jù)中提取事件模式,并將事件檢測問題轉換為模式匹配問題。文獻[16]使用Contour Map作為數(shù)學工具來對事件模式進行建模,進一步提高事件檢測準確性。隨著機器學習和深度學習的發(fā)展,網(wǎng)絡監(jiān)測逐步采用數(shù)據(jù)驅動的機器學習方法,取得了很好的效果。文獻[17]通過主成分分析(Principal Component Analysis,PCA)在線進行降維,以處理輸入數(shù)據(jù)中的無關和冗余數(shù)據(jù)。基于預測值與真實值的偏差,通過動態(tài)閾值法實現(xiàn)網(wǎng)絡監(jiān)測/事件檢測。文獻[18]在多維特征空間中應用了支持向量機(Support Vector Machine,SVM)、k近鄰(k-Nearest Neighbor,k-NN)、高斯混 合模型(Gaussian Mixture Model,GMM)等方法,解決了傳統(tǒng)方法監(jiān)測效率低、誤報率高的問題。此外,文獻[19-20]對時效性展開研究,分別就時間同步和時延問題進行了分析。上述研究的優(yōu)點在于能夠識別較廣泛的事件類型,缺點在于無法識別首次出現(xiàn)的事件,每次都需要重新訓練模型以適應新事件類型。
WSN 中大部分節(jié)點依賴于容量有限的電池供電,能量耗盡將影響節(jié)點的可用性,因此在設計相關信息收集算法時需要考慮到節(jié)點是否有足夠的能量完成數(shù)據(jù)收發(fā)任務。LEACH(Low-Energy Adaptive Clustering Hierarchy)是WSN 中專注于低能耗的最重要協(xié)議之一,LEACH 隨機挑選節(jié)點作為簇首節(jié)點,每個簇首節(jié)點匯集本簇節(jié)點數(shù)據(jù)后傳輸給Sink 節(jié)點,簇首節(jié)點的巨大消耗通過隨機算法均攤到各個節(jié)點上。在LEACH 出現(xiàn)后,文獻[21-22]為了改進能量使用效率,將節(jié)點剩余能量作為簇首節(jié)點選取因素。文獻[23]將簇劃分算法改為基于k-d樹算法的遞歸矩形分區(qū)算法來提升性能。PEGASIS[24]不同于LEACH 以簇來劃分,PEGASIS使用鏈劃分。節(jié)點在收到數(shù)據(jù)后傳遞給后續(xù)節(jié)點,直到最終傳遞到Sink 節(jié)點。PEGASIS 依賴于節(jié)點對全局知識的掌握,節(jié)點使用貪心算法選取下一個最鄰近節(jié)點作為后續(xù)節(jié)點。文獻[25]提出一種自適應數(shù)據(jù)聚合方案,該方案依賴于節(jié)點能量值的上下限,如果低于較低閾值則會進入休眠狀態(tài)。文獻[26]考慮了由能量問題帶來的延遲,提出能量碰撞的概念,即當兩個節(jié)點計劃進行傳輸時,由于其中一個節(jié)點最近的一次活動使得本次沒有足夠能量進行收發(fā),導致此次傳輸無法進行。上述協(xié)議能夠提高網(wǎng)絡的負載均衡性,但是信息感知的延遲通常較大。由于對信息是透明的,因此無法解決大規(guī)模網(wǎng)絡下龐大原始數(shù)據(jù)的傳輸帶來的通信問題。
為了實現(xiàn)持續(xù)及時地收集網(wǎng)絡全局信息的目標,減少網(wǎng)絡延遲,降低網(wǎng)絡傳輸次數(shù)和通信量是其中的重點。在分布式系統(tǒng)中,隨著對把握全局信息的需求的提高,必然會出現(xiàn)全網(wǎng)信息收集和大量的洪泛開銷。為解決其中產(chǎn)生的數(shù)據(jù)傳輸和存儲開銷問題,一個直觀的做法是將數(shù)據(jù)進行壓縮,之后再進行傳輸和存儲。目前通用的壓縮算法可以分為有損數(shù)據(jù)壓縮算法和無損數(shù)據(jù)壓縮算法。前者可以無損恢復壓縮前的數(shù)據(jù),原理是根據(jù)數(shù)據(jù)冗余特性,引入信息墑理論計算的編碼極限,缺點是壓縮效果不明顯,對算力有一定要求,成本較高。有損數(shù)據(jù)壓縮算法針對的大多是多媒體數(shù)據(jù),壓縮后重建的數(shù)據(jù)質量有所損失,如圖像壓縮算法JPEG、視頻壓縮算法H.261、音頻壓縮MP3 和語音壓縮G.711。當分布式系統(tǒng)產(chǎn)生的數(shù)據(jù)具有一些特性時,往往可以采用一些特殊算法,這方面相關的研究有基于數(shù)據(jù)時空冗余性的壓縮算法?;跁r空冗余性的壓縮算法利用了單個節(jié)點所采集的數(shù)據(jù)在時間上的冗余、鄰居節(jié)點采集的數(shù)據(jù)之間的空間冗余性以及單個節(jié)點在關聯(lián)屬性之間的冗余。這類算法采用預測估計技術將實測值和預估值進行差分運算以消除冗余。由于節(jié)點運算和存儲資源受限,通常使用低階編碼進行預測,因此只適用于低精度事件檢測場景。也有研究使用高階多項式最小二乘曲線擬合將采集的數(shù)據(jù)在網(wǎng)管進行解碼。這些算法時間復雜度高,計算量大?;谄娈愔捣纸庖约半x散傅里葉變換的技術在這種場景下壓縮能力強,但是普遍計算量偏大。
基于壓縮感知算法是根據(jù)陶哲軒等人提出的壓縮方法,其突破了傳統(tǒng)奈奎斯特采樣定理。壓縮感知相較于其他壓縮算法,不同點在于:信號是稀疏的,數(shù)據(jù)的壓縮和采樣是同步的,壓縮算法和解碼算法之間較獨立。壓縮感知需要的信號是稀疏的,這在大規(guī)模網(wǎng)絡中,尤其是傳感器網(wǎng)絡中非常符合。傳統(tǒng)的壓縮方法是先采樣再壓縮,而壓縮感知同時進行則加快了感知的速度。在資源受限的傳感器網(wǎng)絡中,壓縮和恢復算法的獨立意味著能夠根據(jù)情況靈活設計。文獻[27]使用PCA 分析和Bayes 方法設計了一種在線壓縮恢復方法,通過返回信號恢復誤差到壓縮感知框架來自動調整系統(tǒng)參數(shù),從而動態(tài)適應信號特征。但是壓縮感知的問題在于精度不穩(wěn)定,在信噪比較低、信號波動大時尤其如此。
網(wǎng)絡編碼(Network Coding,NC)[28]是近年來通信領域一個活躍的研究分支,其基本思想是網(wǎng)絡節(jié)點不僅參與數(shù)據(jù)轉發(fā),還參與數(shù)據(jù)處理,這樣可以大幅提高網(wǎng)絡通信性能,但其可行性依賴于特定拓撲結構。在此之前,信息交換不會和其他信息融合。在端到端的信息交換過程中,路徑上的其他節(jié)點起到的作用是簡單的存儲和轉發(fā),即路由交換的功能。節(jié)點不會對原始數(shù)據(jù)進行修改,數(shù)據(jù)包的完整性在整個傳輸過程中不會被破壞。而在網(wǎng)絡編碼中,節(jié)點可以將多個數(shù)據(jù)包混合之后轉發(fā),以提高系統(tǒng)的吞吐量,減少網(wǎng)絡延遲,以及在無線傳感器網(wǎng)絡中減少每比特能量消耗。網(wǎng)絡編碼中對于節(jié)點混合信息的要求是:只要接收節(jié)點有足夠多的Evidence 和Clues 用來重構從發(fā)送節(jié)點發(fā)出的原始數(shù)據(jù)包即可[29]。信息的混合在實現(xiàn)上若為線性操作和非線性操作,稱為線性/非線性編碼,此外還有引入隨機系數(shù)的方法,即隨機線形網(wǎng)絡編碼(Random Linear Network Coding,RLNC)。RLNC 實現(xiàn)更加簡單,但缺點是計算復雜度為O(n3),其中,n為節(jié)點監(jiān)聽到的數(shù)據(jù)包。文獻[30]考慮節(jié)點能耗和網(wǎng)絡壽命問題,提出一種基于網(wǎng)絡編碼的低能耗可靠機會路由算法,該算法通過丟包率和誤碼率來計算失敗概率,從而降低重傳次數(shù)。雖然該方法能降低能耗,延長網(wǎng)絡壽命,但缺點是轉發(fā)集內(nèi)數(shù)據(jù)包過多。文獻[31]將網(wǎng)絡編碼和拓撲控制相結合,提出一種數(shù)學模型,在模型中同時考慮到了傳輸功率和接收能量。該方法使用遺傳算法來搜索最佳方案,可以實現(xiàn)均衡的負載和更長的網(wǎng)絡壽命,但其缺點在于計算過程非常復雜且耗時,在大規(guī)模網(wǎng)絡中尤其如此。文獻[32]提出一種機會網(wǎng)絡編碼(Opportunistic Network Coding,ONC),每個中繼可以選擇編碼之后再發(fā)送,可直接發(fā)送原始數(shù)據(jù)、一次平衡時延和吞吐量。網(wǎng)絡編碼優(yōu)點在于通過對信息進行編碼,利用節(jié)點間多條傳輸路徑,以增加傳輸吞吐量。而節(jié)點需要等待有足夠的數(shù)據(jù)包來完成解碼,這就造成了時間延遲以及能耗問題。為了等待一些數(shù)據(jù)包到達而不得不先存儲已經(jīng)到達的數(shù)據(jù)包,可能會導致緩沖區(qū)溢出或者數(shù)據(jù)包丟失。
2.1.1 網(wǎng)絡模型
本文研究的對象是分布式與節(jié)點能力受限的無線傳感器網(wǎng)絡。將整個網(wǎng)絡表達為G(V,E),一個由節(jié)點Vi和鏈接E組成的無向圖結構,網(wǎng)絡中節(jié)點的個數(shù)使用N或者|G(V,E)|來表示。無線傳感器網(wǎng)絡模型如圖1 所示。
圖1 無線傳感器網(wǎng)絡模型Fig.1 Wireless sensor network model
WSN 使用消息來實現(xiàn)松散時鐘同步,在初始時刻t0系統(tǒng)會完成初始化工作,節(jié)點通過與鄰居的消息來同步推進本地時鐘。在初始化階段,節(jié)點會被賦予一個唯一的初始混沌編碼,以及一個素數(shù)生成規(guī)則函數(shù)πi(t)。函數(shù)πi(t)用來生產(chǎn)輔助運算數(shù)組。素數(shù)生成函數(shù)可以按照某個特定規(guī)則產(chǎn)生,例如順序取第(i+nt)個素數(shù)作為第i個節(jié)點的第t輪時鐘的素數(shù),即:
2.1.2 節(jié)點模型
在本文的設計中,節(jié)點需要像神經(jīng)元一樣能夠對外界事件做出響應,根據(jù)響應計算并更新本地編碼。而出于節(jié)能的考慮,節(jié)點應該在完成計算時進入休眠,所以節(jié)點應該處在動態(tài)的變化中。為此,為網(wǎng)絡和節(jié)點設計以下4 種狀態(tài):
1)局部收斂態(tài):當前時鐘輪和上一時鐘輪的編碼值差值小于閾值?,即
2)全局收斂態(tài):所有節(jié)點都進入局部收斂的狀態(tài),即全局處于收斂狀態(tài)。
3)局部穩(wěn)定態(tài):節(jié)點相鄰兩輪編碼差值小于閾值?,或上輪狀態(tài)為穩(wěn)定態(tài)且本輪無鄰居節(jié)點的擾動。
4)局部擾動態(tài):在節(jié)點處于局部穩(wěn)定態(tài)下,本地節(jié)點的鄰居有節(jié)點加入或者退出。
在不同狀態(tài)下,節(jié)點運行不同算法過程來計算編碼,主要分為擾動計算和收斂計算兩個部分。
2.2.1 擾動模塊
在初始化時網(wǎng)絡處在全局收斂狀態(tài),各個節(jié)點處在局部收斂狀態(tài)。當節(jié)點Vi檢測到直接的拓撲變化事件,或者通過鄰居節(jié)點的編碼獲知網(wǎng)絡某處的拓撲發(fā)生變化時,那么就會進入到擾動態(tài),執(zhí)行擾動計算。如果沒有事件發(fā)生則在下輪重新進行檢測,本輪編碼保持不變,即。具體步驟如下:
1)擾動檢測:分為直接檢測和鄰居編碼間接檢測,兩者都只有在節(jié)點處于收斂態(tài)下才有效。如果在非收斂態(tài)下檢測到,直接檢測的結果將會被延遲觸發(fā),間接檢測結果將直接被忽略。則直接檢測即節(jié)點通過心跳等方式檢測到鄰居節(jié)點的上下線事件,間接方式為檢測是否有鄰居節(jié)點的編碼出現(xiàn)擾動信號。表達式如下:
若滿足條件則進入局部擾動態(tài),繼續(xù)執(zhí)行步驟2,否則跳出,并在下輪進行檢測。
2)編碼規(guī)范化處理:將尖峰信號處理取倒數(shù),其他編碼不變。
3)計算鄰域幾何均值:根據(jù)上一步統(tǒng)一規(guī)范化處理后的編碼計算其幾何均值。
5)完成擾動:推出擾動計算,進入收斂計算過程。
通過擾動計算,節(jié)點將事件產(chǎn)生的擾動信息以類Gossip 方式傳播到全網(wǎng)絡中,從而讓所有的節(jié)點都能感知到該擾動,這種機制保證了本文算法4 個特性中的傳播性。系統(tǒng)完成一次擾動計算之后馬上就進入到收斂計算,在收斂計算過程中,節(jié)點不會再次進行擾動計算,這可以避免網(wǎng)絡中出現(xiàn)同一個事件消息多次被識別為擾動源。
2.2.2 收斂模塊
當結束擾動計算后,收斂計算將會持續(xù)多輪直到本地節(jié)點進入到局部收斂態(tài)。如果將擾動計算過程視作擾動產(chǎn)生的全局信息的傳輸過程,那么收斂計算則可以看作對該信息的存儲過程。收斂計算的具體步驟如下:
1)編碼規(guī)范化處理:計算鄰域幾何均值,過程同擾動模塊。
2)編碼更新:如果編碼的差值小于閾值?,則進入到局部收斂狀態(tài),編碼無須更新,否則更新編碼。
3)狀態(tài)更新:如果當前狀態(tài)被評估為非局部收斂狀態(tài),那么不退出當前收斂計算過程,下一輪將重復步驟1~步驟3。如果當前已經(jīng)是局部收斂狀態(tài),那么再評估連續(xù)處于收斂狀態(tài)的輪數(shù)是否大于D(D為網(wǎng)絡直徑),如果大于則進入到穩(wěn)定態(tài),否則節(jié)點將依然處于局部收斂狀態(tài)并將繼續(xù)執(zhí)行上述算法,直到滿足穩(wěn)定態(tài)條件退出當前計算過程。節(jié)點狀態(tài)變化過程如圖2 所示。
圖2 節(jié)點狀態(tài)變化過程Fig.2 Process of node status change
2.2.3 整體計算模型
在網(wǎng)絡正式運行前,需要完成節(jié)點的初始化工作,此時節(jié)點處于局部收斂狀態(tài)。節(jié)點之間通過消息同步時鐘,節(jié)點持續(xù)在每輪時鐘下監(jiān)測鄰居節(jié)點的活躍性,執(zhí)行擾動模塊的算法過程。當檢測到擾動信號時,執(zhí)行收斂模塊過程,2 個模塊和4 種狀態(tài)的交替構成了整體算法過程,如圖3 所示。
圖3 節(jié)點的整體計算過程Fig.3 Overall calculation process of nodes
2.2.4 性質
基本性質主要有以下4 種:
1)傳遞性
定義:給定一個連通網(wǎng)絡G(V,E),當完成初始化工作后,若網(wǎng)絡某處發(fā)生拓撲事件變化,則時空編碼構造的算法過程會將該事件傳遞到網(wǎng)絡所有節(jié)點下,使得節(jié)點由全局穩(wěn)定態(tài)進入局部擾動態(tài),進而完成計算編碼過程。
證明:假設拓撲事件發(fā)生時與事件源所在節(jié)點為Vi,其所關聯(lián)的鄰居節(jié)點Ni一定能直接檢測到事件信息并運行擾動模塊,傳遞尖峰編碼。當鄰居節(jié)點Ni產(chǎn)生尖峰編碼后,節(jié)點的鄰居節(jié)點將在本時鐘輪收到尖峰編碼,在下一個時鐘輪中,將由局部收斂態(tài)進入到局部擾動態(tài)。同樣地,鄰居節(jié)點也會生成尖峰編碼,并傳遞給其鄰居節(jié)點。由于給定的網(wǎng)絡為連通網(wǎng)絡,且拓撲事件不改變連通性,那么鄰居節(jié)點Ni發(fā)出的尖峰編碼將最多經(jīng)歷|D| 個時鐘輪就使得所有的節(jié)點從穩(wěn)定態(tài)進入局部擾動態(tài),這里的|D|為網(wǎng)絡的直徑大小。也就是說,時空編碼構造過程能夠在最多|D|個時鐘輪之后將網(wǎng)絡中的某處發(fā)生的拓撲事件傳遞到全網(wǎng)所有節(jié)點,即傳遞性得證。
2)收斂性
定義:給定一個連通網(wǎng)絡G(V,E),當網(wǎng)絡中某處產(chǎn)生了拓撲事件,所有節(jié)點從全局收斂態(tài)進入到局部擾動態(tài)(傳遞性),收斂性將保證網(wǎng)絡所有節(jié)點按照收斂模塊算法運行有限時間之后重新收斂到全局穩(wěn)定態(tài)。
定理1任意節(jié)點Vi的編碼可以表示為,其中,αi是代數(shù)數(shù),pi是素數(shù)[33]。
證明:網(wǎng)絡G(V,E)的某處發(fā)生了拓撲事件,節(jié)點將不斷執(zhí)行收斂模塊算法,更新本地編碼值,變化的編碼值始終處在范圍(0,1)中。由定理1 可知,在第t時鐘輪,節(jié)點Vi的編碼可以表示如下:
式(10)說明,節(jié)點在執(zhí)行收斂模塊算法過程中,節(jié)點的編碼值不斷遞減。而收斂模塊中當節(jié)點的編碼值小于閾值?時,編碼將保持不變,多輪之后節(jié)點進入本地收斂態(tài)。上述過程說明,節(jié)點在多輪時鐘之后將進入本地收斂態(tài),當所有節(jié)點都進入本地收斂態(tài)后,全網(wǎng)狀態(tài)則進入全局收斂態(tài)。
3)因果性
定義:給定一個連通網(wǎng)絡G(V,E),在相同的初始化配置和相同輸入的情況下,時空編碼的算法過程將產(chǎn)生相同的編碼序列。而在初始化配置不同和(或)輸入不同的情況下,算法過程將產(chǎn)生不同的編碼序列,即以下3 種情況:(1)相同初始條件,不同的拓撲事件原因將產(chǎn)生不同結果;(2)不同初始條件,相同的拓撲事件原因將產(chǎn)生不同結果;(3)不同初始條件,不同的拓撲事件原因產(chǎn)生不同結果。
定理2對于一個連通網(wǎng)絡G(V,E),在某個時刻下,全局的拓撲連接矩陣表示為C,全局編碼集合表示為X。在經(jīng)過一次拓撲事件后,全局拓撲連接改變?yōu)镃1,對于任意兩個網(wǎng)絡中的節(jié)點Vi、Vj,i≠j,必然有
定理3對于一個連通網(wǎng)絡G(V,E),在某時刻下,全局的拓撲連接矩陣表示為C,全局編碼集合表示為X。當經(jīng)過兩次拓撲事件后,全局拓撲發(fā)生改變:
由此造成的全局網(wǎng)絡中各個節(jié)點的本地編碼均不相同,有:
其中:Vi、Vj為網(wǎng)絡中的節(jié)點,且允許i=j的情況,這種情況即相同節(jié)點在不同的拓撲結構下編碼是不同的。
證明:由以上兩個引理可以推出在相同初始配置和相同輸入情況下編碼序列相同。而不滿足任意一個條件都將使得編碼序列不同,有:(1)相同初始條件,不同的事件序列導致不同的全局編碼序列;(2)不同初始條件,相同的事件序列有不同全局編碼序列;(3)不同初始條件和不同時間序列有不同全局編碼序列,即事件原因和結果一一對應。
4)確定性
定義:在相同的網(wǎng)絡初始化條件下,給定系統(tǒng)相同的輸入,時空編碼算法過程總是到達相同的網(wǎng)絡狀態(tài),產(chǎn)生一致的輸出結果。
證明:由時空編碼算法的數(shù)學過程可知,涉及編碼計算的函數(shù)均為單射的確定性函數(shù)。因此,給定相同的初始條件,保證節(jié)點能正確執(zhí)行編碼算法的情況下,時空編碼運行的整個過程是確定的,不會有隨機因素參與并改變執(zhí)行的結果。其演化過程在相空間中表現(xiàn)為固定的軌跡。
本節(jié)提出基于非定域感知理論的時空編碼方法,將非定域感知理論的拓撲感知場景擴展到普遍的信息感知場景下,并給出數(shù)據(jù)收集與感知的具體編碼過程。
在網(wǎng)絡處于全局收斂的狀態(tài)下,節(jié)點或者邊的增加或者刪除會生成一個尖峰信號,尖峰信號將會被記錄在節(jié)點的本地編碼中,最終被全網(wǎng)所有節(jié)點感知到。這種蝴蝶效應的結果將會被反映到網(wǎng)絡所有的節(jié)點的本地編碼中。節(jié)點將本地編碼運行分解算法得到傳播路徑,從可以定位得到擾動源節(jié)點,實現(xiàn)非定域感知。如果將擾動源節(jié)點固定為兩個節(jié)點,并將其映射為0 和1,那么可以將普遍的信息映射到每個節(jié)點的本地編碼中,編碼過程如圖4 所示。如算法1 所示,將一系列事件信息以0-1 序列形式注入到網(wǎng)絡中,經(jīng)過節(jié)點反復的收斂和傳播計算,這些信息將會被編碼存儲在網(wǎng)絡所有節(jié)點中。
圖4 編碼過程Fig.4 Encoding process
算法1基于非定域感知理論的混沌編碼過程
根據(jù)前文對非定域感知理論的討論可知,本文算法具有因果性和確定性,在某個時間點下產(chǎn)生的事件將會唯一地被記錄在網(wǎng)絡中各個節(jié)點的本地編碼中,并能夠唯一地被解析恢復?;谇懊娴木幋a算法,本文提出一個基于編碼序列的解碼方案,解碼過程如圖5 所示。如算法2 所示,此方案利用基于掃描線的搜索算法定位引起上一次網(wǎng)絡拓撲變化的源節(jié)點,通過多次定位事件源節(jié)點來解析出源事件序列。對于節(jié)點來說,只需在解碼時執(zhí)行此算法,在一般情況下只需要接受鄰居編碼并更新本地編碼即可。通過這種策略,本文將通信和存儲域上的開銷轉移到計算域上的開銷,突破了節(jié)點存儲和通信能力的限制,從而能達到持續(xù)地、實時地、非定域地感知信息。
圖5 解碼過程Fig.5 Decoding process
算法2非定域時空編碼解碼過程
實驗使用Ubuntu 18.04 LTS 版本為操作系統(tǒng),CPU 為i7-9750H,軟件環(huán)境為Java17.0.2,JVM 為HotSpotTM64 bit Server VM。實驗通過多線程模擬節(jié)點,使用線程的創(chuàng)建,銷毀仿真節(jié)點的加入退出的行為。節(jié)點之間的通信使用Socket 通信方式來完成,這一方案也有利于模擬實際通信過程中的丟包、重連等情況。另外,系統(tǒng)中的松散時鐘部分使用了基于消息的同步機制來進行模擬。實驗將網(wǎng)絡分為編碼輸入節(jié)點、普通節(jié)點以及在普通節(jié)點中隨機選取的節(jié)點作為解碼節(jié)點。實驗將編碼固定輸入節(jié)點表示為NODE0、NODE1,以拓撲變化事件信息源固定為編碼輸入節(jié)點的拓撲變化事件,將感知信息抽象為0-1 序列,隨機選擇要輸入的0-1 序列信息Sin=b0,b1,…,bn,其長度為n=|Sin|,bi?0,1。輸入完畢后網(wǎng)絡處于全局收斂狀態(tài),此時隨機選取節(jié)點NODEr作為解碼節(jié)點,運行算法2,解碼得到序列Sout=B0,B1,…,Bm,比較Sin和Sout。改變網(wǎng)絡拓撲、網(wǎng)絡規(guī)模|S|以及輸入序列Sin的長度,檢測算法在不同場景下的表現(xiàn)。
為驗證本文方法的正確性和有效性,以網(wǎng)絡中的拓撲變化事件作為信息源進行測試,實驗將從準確度、通信開銷、存儲開銷、計算開銷、收斂速率等方面進行評估。
1)準確度。如圖6 所示,在節(jié)點數(shù)目較多的網(wǎng)絡中,對于中短序列檢測準確度接近于100%,長序列檢測準確度下降。當序列長度一致時,節(jié)點數(shù)目越多的網(wǎng)絡,檢測度越高。對此現(xiàn)象可以解釋為當節(jié)點數(shù)量增加時,群體的整體存儲計算能力增強,同時對應的抗干擾能力也會增強,從而增加了信息恢復準確度。而在網(wǎng)絡規(guī)模確定的情況下,準確度隨著輸入序列長度增加而降低。這是由于時空編碼依賴于浮點數(shù)計算,而計算機二進制表達浮點數(shù)的精度有限,因此出現(xiàn)準確度下降問題。
圖6 不同網(wǎng)絡規(guī)模和本地編碼大小下的準確率Fig.6 Accuracy under different network sizes and local code sizes
2)通信復雜度。在本文提出的算法中,每個節(jié)點只需和m個鄰居節(jié)點通信,其通信復雜度為O(mn),其中,m為節(jié)點平均的鄰居個數(shù),在最好情況下為m=1。在理論的最壞情況下,如在全連接的網(wǎng)絡拓撲中,每個節(jié)點都和其他節(jié)點連接,最差通信復雜度為O(n2),所以編碼消息整體通信復雜度為O(n)。然而,本文是通過將本地編碼搭載在Beacon消息上來完成鄰居節(jié)點之間的通信的,所以不會產(chǎn)生額外的通信開銷,從額外通信數(shù)據(jù)角度來看,本文的通信開銷為常數(shù)級。實驗中將通信次數(shù)C和通信數(shù)據(jù)包大小S的乘積來衡量通信開銷CCostc,通信包含數(shù)據(jù)輸入并存儲在網(wǎng)絡中的過程store,也包括數(shù)據(jù)從網(wǎng)絡中取出來的過程query,總的開銷表示為:CCostc=Cstore×Sstore+Cstore×Sstore。將時空編碼方法和其他WSN 存儲相關方法進行比較,包括基于分布式存儲方式使用Double Rulings(DR)[34]方法來解決數(shù)據(jù)可用性問題方法、基于分布式存儲使用糾刪碼系統(tǒng)RRNS 來提高數(shù)據(jù)安全性的方法[35]、基于本地存儲的Directed-Diffusion(DD)方法[36]。不同序列長度和網(wǎng)絡規(guī)模下通信開銷如圖7 所示。在圖7(a)中,本文方法隨著網(wǎng)絡規(guī)模的增長呈線形增長,這是因為在輸入序列數(shù)據(jù)較小的情況下,編碼的開銷不可忽略。而在輸入比特序列增加的情況下,發(fā)現(xiàn)本文方法的通信開銷逐漸逼近到了常數(shù)級別。理論上Directed-Diffusion 由于需要使用洪泛的方式獲取數(shù)據(jù),從而產(chǎn)生了較高的開銷。RRNS 需要將數(shù)據(jù)切分成數(shù)據(jù)塊,并額外生成校驗數(shù)據(jù)塊,增加了額外的通信次數(shù)和數(shù)據(jù)量。相比之下,本文的方法在通信開銷方面有更好的表現(xiàn)。
圖7 不同序列長度和網(wǎng)絡規(guī)模下的通信開銷Fig.7 Communication overhead under different sequence lengths and network scales
3)存儲復雜度。本文方法中每個節(jié)點只需存儲鄰居節(jié)點發(fā)來的上輪編碼,以及節(jié)點自身的編碼,節(jié)點只需不斷利用鄰居節(jié)點的編碼計算并更新自身編碼即可。類似通信復雜度,節(jié)點的存儲開銷為O(m),其中,m為節(jié)點的鄰居節(jié)點個數(shù),是一個常數(shù),所以整體存儲開銷為O(1)。
如圖8 所示,DR 方法需要將數(shù)據(jù)把副本復制到ReplicateCurve 上的節(jié)點,所以會產(chǎn)生大量存儲?;诩m刪碼的方法需要額外存儲校驗數(shù)據(jù),所以會產(chǎn)生少量冗余(這里糾刪碼冗余度為1.33)。從實驗結果可以看出,本文方法相比其他方法有明顯的優(yōu)勢。
圖8 不同序列長度和網(wǎng)絡規(guī)模下的存儲開銷Fig.8 Storage overhead under different sequence lengths and network scales
通過理論分析,本文編碼計算過程的復雜度為O(m),解碼為O(n2),對比其他算法具有較低的復雜度,算法的整體相關復雜度如表1 所示。
表1 通信、存儲和計算復雜度 Table 1 Communication,storage,and calculation complexity
4)收斂速率。在Mesh 拓撲結構中,對網(wǎng)絡中節(jié)點的平均收斂輪數(shù)進行測試,網(wǎng)絡中節(jié)點的收斂輪數(shù)大致呈正態(tài)分布,這從實驗的角度進一步驗證了本文算法的收斂性。實驗結果如圖9 所示,網(wǎng)絡中的大部分節(jié)點都能在有限時間內(nèi)完成收斂計算,能夠在一定程度上應對實時性的要求。
圖9 收斂輪數(shù)及頻率Fig.9 Convergence rounds and frequency
為了解決無線傳感器網(wǎng)絡中的及時持續(xù)收集全局信息、巨大的網(wǎng)絡通信量與較高的時延之間的問題,本文借助網(wǎng)絡狀態(tài)信息和計算空間時空結構之間的數(shù)學關聯(lián),提出在存儲、通信、計算上常數(shù)開銷的時空編碼算法,實現(xiàn)對拓撲變化信息的計算感知,解決通過洪泛手段收集全局信息帶來的通信開銷問題。實驗結果表明,該方法具有良好特性。后續(xù)將研究在節(jié)能、通信受限、存儲有限等場景下的優(yōu)化問題,提高時空編碼方法的實用性。