基于超越數論的無線傳感器網絡時空編碼方法

胡宗升，邢 凱，2，許 靜

（1.中國科學技術大學 計算機科學與技術學院，合肥 230026；2.中國科學技術大學 蘇州高等研究院，江蘇 蘇州 215123）

0 概述

無線傳感器網絡（Wireless Sensor Network，WSN）一般由一系列能夠感知周圍環境，使用無線信道進行通信的傳感器節點組成，是一種能夠進行感知、處理、存儲和傳輸感知區域信息的分布式自組織網絡，其在國防軍事、防災預警、氣候監測、交通運輸、環境與農業等領域具有廣泛的應用。在這些領域中，存在大量應用需要WSN 能夠快速、持續地收集全局信息，并及時做出決策和調度。因此，信息的收集匯聚是無線傳感器網絡的主要任務之一。但是，在數據多跳匯聚過程中，中繼節點的存儲轉發產生了大量的通信、存儲和能量開銷。而無線傳感節點只有有限的通信帶寬、存儲容量以及能量。在大規模分布式環境下，傳統方法難以調和其信息通信、存儲、能量約束與全局信息收集的持續性和及時性要求之間的沖突。為解決這一挑戰，研究人員針對大規模分布式無線傳感器網絡在信息收集匯聚方面的傳輸和能耗問題進行了大量研究［1-3］。

在信息收集匯聚任務中，無線傳感器網絡一般通過網絡的各個節點將其所感知信息經由中間節點多跳傳輸匯總到基站。這種方式的缺點主要是：依賴中間節點的路由中繼，如果中間節點故障，則會導致某些節點信息無法到達Sink 節點，繼而無法到達基站，因此需要常態化地、持續地監控并維護網絡，開銷巨大；受限于單點失效問題，一旦匯聚節點失效，就意味著網絡可用性降低甚至不可用，對匯聚節點選取要求高；通信和能耗問題，節點離基站越近，通過該節點的信息越密集，中繼通信負載越大，能耗也越高，會帶來較嚴重的負載均衡問題，當基站附近的節點在耗盡能量、通信帶寬和存儲空間后，會導致可用性問題。

針對無線傳感器網絡在信息匯聚任務中的匯聚節點失效和中繼路由可靠性問題，當前研究往往采用骨干拓撲的方式，利用簇（如LEACH［4-5］算法）或者樹的方式（如LPT［6］算法）匯集數據，例如網絡根據拓撲位置或能量等特性將網絡劃分為多個簇，或通過分布式匯聚算法形成樹狀等骨干拓撲，節點收集信息后發送給骨干拓撲節點并通過骨干網匯集信息。這種方式不依賴于中心節點，傳感器節點只需和附近鄰居節點通信，以自組織骨干網通過多跳的方式協作進行信息傳輸。相應地，節點也需要更多通信開銷來完成骨干網拓撲維護、時間同步、節點選舉等工作，從而導致較高的網絡延遲和維護開銷，因此對于全局信息收集有實時性要求的場景，例如防災預警、入侵檢測等難以提供有效保障，同時每個節點都有持續的通信和維護開銷，進一步擠壓了節點的通信和續航能力。然而，隨著對掌握全局信息需求的提高，傳統的信息匯聚方法不可避免地帶來全網范圍的信息收集和大量的中繼存儲轉發開銷，這些通信和存儲所帶來的能耗、帶寬及存儲開銷巨大。因此，如何降低網絡中的傳輸/存儲開銷一直是大規模分布式無線傳感器網絡信息收集與匯聚研究中的重點方向。

針對無線傳感器網絡在信息匯聚任務中的海量信息傳輸/存儲開銷問題，一個直觀的做法是將數據進行編碼/壓縮之后再進行傳輸和存儲。如面向多播傳輸的網絡編碼方法［7-9］，基于圖論中最大流最小割原理保證了多播網絡在確定性路徑下可以達到網絡最大信息流，直觀上減少了網絡傳輸次數，然而該方法在信息匯聚和單播網絡通信應用中因拓撲/路由的不確定性而難以被廣泛應用。壓縮感知［10］（Compressor Sensing，CS）方法突破了傳統奈奎斯特采樣定理。不同于傳統的壓縮方法是先采樣再壓縮，壓縮感知則是采樣與壓縮同時進行，且解碼算法獨立于壓縮算法，因此尤其適合資源受限的傳感器網絡，壓縮和恢復算法的獨立意味著能夠根據傳輸路徑的變化而靈活地進行感知和數據重建。但是，壓縮感知是有損壓縮，其精度依賴于感知數據分布，當數據分布變化時穩定性欠佳，在信噪比較低和分布波動大時尤其如此。不難看出，信息收集匯聚過程中的信息壓縮效率和相關算法的通用性始終是該研究領域的重要挑戰。

從以上研究進展可以看出，以計算開銷來降低/部分替代通信和存儲帶來的開銷，是資源受限的大規模分布式無線傳感器網絡的信息通信、存儲和能量約束與全局信息收集的持續性和及時性要求之間矛盾的一個重要趨勢變化，也是當前大規模分布式無線傳感器網絡研究的重點，即存算通信一體化研究。

針對大規模分布式無線傳感器網絡中以存儲轉發方式為主的傳統信息收集匯聚方式，本文提出一種以計算方式降低/部分替代通信和存儲開銷的存算通信一體化新方法，并給出相關理論分析和論證。

1 相關工作

對信息的收集和匯聚是信息系統持續優化和決策的前提條件，其中網絡拓撲的感知與維護在信息匯聚過程中不可缺少。

拓撲感知（Topology Sensing）是分布式網絡感知和維護拓撲信息的重要方法。Topology Sensing可以分為In-network 和Out-network 兩類。早期的拓撲感知的工作主要集中在網絡感知方面，并通過交換路由信息來實現。例如使用SNMP 協議主動監測網絡中協議、接口、速度等信息來生成完整的網絡視覺地圖。也有研究利用開放最短路徑OSPF 來跟蹤域內拓撲信息，以此來構建一個及時準確的拓撲信息。Out-network 受到了更廣泛的關注，文獻［11］將信息傳遞過程視作一個Hawkes 過程，從有限的被動網絡活動觀測來表征和分析無線網絡，檢測現有拓撲的變化以及提取網絡中信息流的信息，并利用模型和數據推斷網絡事件之間的聯系，識別出事件鏈。文獻［12］考慮WSN 中負載不均勻的問題，利用勢博弈理論，提出了拓撲控制算法BLTC。該算法能夠評估附近節點，根據效用函數選擇節點構建拓撲，將節點能耗均勻問題轉換為博弈問題，能夠有效提高網絡壽命，但缺點是網絡的博弈階段較長，延長了數據收集過程的延遲。文獻［13］進一步對網絡拓撲修復進行了調研，總結和分析了各類拓撲修復方法的優缺點。

無線傳感器被大量應用于監測預警的場景，如何保證這些場景下信息收集的準確性、實時性以及持續性是非常關鍵的問題。事件檢測的相關工作有基于閾值的方法、基于模式的方法和基于學習的方法［14］。在基于閾值的網絡監測/事件檢測研究中，閾值通常由領域專家定義，當檢測到的值高于（低于）閾值時，會觸發通知事件，并通過網絡傳輸到基站或外部系統，其優點是簡單，缺點是當數據需要傳輸到系統外部進行檢測評估時，增加了通信開銷，降低了事件檢測及時性。文獻［15］基于模式匹配的監測方法從感知數據中提取事件模式，并將事件檢測問題轉換為模式匹配問題。文獻［16］使用Contour Map作為數學工具來對事件模式進行建模，進一步提高事件檢測準確性。隨著機器學習和深度學習的發展，網絡監測逐步采用數據驅動的機器學習方法，取得了很好的效果。文獻［17］通過主成分分析（Principal Component Analysis，PCA）在線進行降維，以處理輸入數據中的無關和冗余數據。基于預測值與真實值的偏差，通過動態閾值法實現網絡監測/事件檢測。文獻［18］在多維特征空間中應用了支持向量機（Support Vector Machine，SVM）、k近鄰（k-Nearest Neighbor，k-NN）、高斯混 合模型（Gaussian Mixture Model，GMM）等方法，解決了傳統方法監測效率低、誤報率高的問題。此外，文獻［19-20］對時效性展開研究，分別就時間同步和時延問題進行了分析。上述研究的優點在于能夠識別較廣泛的事件類型，缺點在于無法識別首次出現的事件，每次都需要重新訓練模型以適應新事件類型。

WSN 中大部分節點依賴于容量有限的電池供電，能量耗盡將影響節點的可用性，因此在設計相關信息收集算法時需要考慮到節點是否有足夠的能量完成數據收發任務。LEACH（Low-Energy Adaptive Clustering Hierarchy）是WSN 中專注于低能耗的最重要協議之一，LEACH 隨機挑選節點作為簇首節點，每個簇首節點匯集本簇節點數據后傳輸給Sink 節點，簇首節點的巨大消耗通過隨機算法均攤到各個節點上。在LEACH 出現后，文獻［21-22］為了改進能量使用效率，將節點剩余能量作為簇首節點選取因素。文獻［23］將簇劃分算法改為基于k-d樹算法的遞歸矩形分區算法來提升性能。PEGASIS［24］不同于LEACH 以簇來劃分，PEGASIS使用鏈劃分。節點在收到數據后傳遞給后續節點，直到最終傳遞到Sink 節點。PEGASIS 依賴于節點對全局知識的掌握，節點使用貪心算法選取下一個最鄰近節點作為后續節點。文獻［25］提出一種自適應數據聚合方案，該方案依賴于節點能量值的上下限，如果低于較低閾值則會進入休眠狀態。文獻［26］考慮了由能量問題帶來的延遲，提出能量碰撞的概念，即當兩個節點計劃進行傳輸時，由于其中一個節點最近的一次活動使得本次沒有足夠能量進行收發，導致此次傳輸無法進行。上述協議能夠提高網絡的負載均衡性，但是信息感知的延遲通常較大。由于對信息是透明的，因此無法解決大規模網絡下龐大原始數據的傳輸帶來的通信問題。

為了實現持續及時地收集網絡全局信息的目標，減少網絡延遲，降低網絡傳輸次數和通信量是其中的重點。在分布式系統中，隨著對把握全局信息的需求的提高，必然會出現全網信息收集和大量的洪泛開銷。為解決其中產生的數據傳輸和存儲開銷問題，一個直觀的做法是將數據進行壓縮，之后再進行傳輸和存儲。目前通用的壓縮算法可以分為有損數據壓縮算法和無損數據壓縮算法。前者可以無損恢復壓縮前的數據，原理是根據數據冗余特性，引入信息墑理論計算的編碼極限，缺點是壓縮效果不明顯，對算力有一定要求，成本較高。有損數據壓縮算法針對的大多是多媒體數據，壓縮后重建的數據質量有所損失，如圖像壓縮算法JPEG、視頻壓縮算法H.261、音頻壓縮MP3 和語音壓縮G.711。當分布式系統產生的數據具有一些特性時，往往可以采用一些特殊算法，這方面相關的研究有基于數據時空冗余性的壓縮算法。基于時空冗余性的壓縮算法利用了單個節點所采集的數據在時間上的冗余、鄰居節點采集的數據之間的空間冗余性以及單個節點在關聯屬性之間的冗余。這類算法采用預測估計技術將實測值和預估值進行差分運算以消除冗余。由于節點運算和存儲資源受限，通常使用低階編碼進行預測，因此只適用于低精度事件檢測場景。也有研究使用高階多項式最小二乘曲線擬合將采集的數據在網管進行解碼。這些算法時間復雜度高，計算量大。基于奇異值分解以及離散傅里葉變換的技術在這種場景下壓縮能力強，但是普遍計算量偏大。

基于壓縮感知算法是根據陶哲軒等人提出的壓縮方法，其突破了傳統奈奎斯特采樣定理。壓縮感知相較于其他壓縮算法，不同點在于：信號是稀疏的，數據的壓縮和采樣是同步的，壓縮算法和解碼算法之間較獨立。壓縮感知需要的信號是稀疏的，這在大規模網絡中，尤其是傳感器網絡中非常符合。傳統的壓縮方法是先采樣再壓縮，而壓縮感知同時進行則加快了感知的速度。在資源受限的傳感器網絡中，壓縮和恢復算法的獨立意味著能夠根據情況靈活設計。文獻［27］使用PCA 分析和Bayes 方法設計了一種在線壓縮恢復方法，通過返回信號恢復誤差到壓縮感知框架來自動調整系統參數，從而動態適應信號特征。但是壓縮感知的問題在于精度不穩定，在信噪比較低、信號波動大時尤其如此。

網絡編碼（Network Coding，NC）［28］是近年來通信領域一個活躍的研究分支，其基本思想是網絡節點不僅參與數據轉發，還參與數據處理，這樣可以大幅提高網絡通信性能，但其可行性依賴于特定拓撲結構。在此之前，信息交換不會和其他信息融合。在端到端的信息交換過程中，路徑上的其他節點起到的作用是簡單的存儲和轉發，即路由交換的功能。節點不會對原始數據進行修改，數據包的完整性在整個傳輸過程中不會被破壞。而在網絡編碼中，節點可以將多個數據包混合之后轉發，以提高系統的吞吐量，減少網絡延遲，以及在無線傳感器網絡中減少每比特能量消耗。網絡編碼中對于節點混合信息的要求是：只要接收節點有足夠多的Evidence 和Clues 用來重構從發送節點發出的原始數據包即可［29］。信息的混合在實現上若為線性操作和非線性操作，稱為線性/非線性編碼，此外還有引入隨機系數的方法，即隨機線形網絡編碼（Random Linear Network Coding，RLNC）。RLNC 實現更加簡單，但缺點是計算復雜度為O（n3），其中，n為節點監聽到的數據包。文獻［30］考慮節點能耗和網絡壽命問題，提出一種基于網絡編碼的低能耗可靠機會路由算法，該算法通過丟包率和誤碼率來計算失敗概率，從而降低重傳次數。雖然該方法能降低能耗，延長網絡壽命，但缺點是轉發集內數據包過多。文獻［31］將網絡編碼和拓撲控制相結合，提出一種數學模型，在模型中同時考慮到了傳輸功率和接收能量。該方法使用遺傳算法來搜索最佳方案，可以實現均衡的負載和更長的網絡壽命，但其缺點在于計算過程非常復雜且耗時，在大規模網絡中尤其如此。文獻［32］提出一種機會網絡編碼（Opportunistic Network Coding，ONC），每個中繼可以選擇編碼之后再發送，可直接發送原始數據、一次平衡時延和吞吐量。網絡編碼優點在于通過對信息進行編碼，利用節點間多條傳輸路徑，以增加傳輸吞吐量。而節點需要等待有足夠的數據包來完成解碼，這就造成了時間延遲以及能耗問題。為了等待一些數據包到達而不得不先存儲已經到達的數據包，可能會導致緩沖區溢出或者數據包丟失。

2 基于超越數論計算空間的時空編碼構造方法及其特性研究

2.1 計算空間中的無線傳感器網絡模型

2.1.1 網絡模型

本文研究的對象是分布式與節點能力受限的無線傳感器網絡。將整個網絡表達為G(V,E)，一個由節點Vi和鏈接E組成的無向圖結構，網絡中節點的個數使用N或者|G(V,E)|來表示。無線傳感器網絡模型如圖1 所示。

圖1 無線傳感器網絡模型Fig.1 Wireless sensor network model

WSN 使用消息來實現松散時鐘同步，在初始時刻t0系統會完成初始化工作，節點通過與鄰居的消息來同步推進本地時鐘。在初始化階段，節點會被賦予一個唯一的初始混沌編碼，以及一個素數生成規則函數πi(t)。函數πi(t)用來生產輔助運算數組。素數生成函數可以按照某個特定規則產生，例如順序取第(i+nt)個素數作為第i個節點的第t輪時鐘的素數，即：

2.1.2 節點模型

在本文的設計中，節點需要像神經元一樣能夠對外界事件做出響應，根據響應計算并更新本地編碼。而出于節能的考慮，節點應該在完成計算時進入休眠，所以節點應該處在動態的變化中。為此，為網絡和節點設計以下4 種狀態：

1）局部收斂態：當前時鐘輪和上一時鐘輪的編碼值差值小于閾值?，即

2）全局收斂態：所有節點都進入局部收斂的狀態，即全局處于收斂狀態。

3）局部穩定態：節點相鄰兩輪編碼差值小于閾值?，或上輪狀態為穩定態且本輪無鄰居節點的擾動。

4）局部擾動態：在節點處于局部穩定態下，本地節點的鄰居有節點加入或者退出。

2.2 節點編碼計算模型

在不同狀態下，節點運行不同算法過程來計算編碼，主要分為擾動計算和收斂計算兩個部分。

2.2.1 擾動模塊

在初始化時網絡處在全局收斂狀態，各個節點處在局部收斂狀態。當節點Vi檢測到直接的拓撲變化事件，或者通過鄰居節點的編碼獲知網絡某處的拓撲發生變化時，那么就會進入到擾動態，執行擾動計算。如果沒有事件發生則在下輪重新進行檢測，本輪編碼保持不變，即。具體步驟如下：

1）擾動檢測：分為直接檢測和鄰居編碼間接檢測，兩者都只有在節點處于收斂態下才有效。如果在非收斂態下檢測到，直接檢測的結果將會被延遲觸發，間接檢測結果將直接被忽略。則直接檢測即節點通過心跳等方式檢測到鄰居節點的上下線事件，間接方式為檢測是否有鄰居節點的編碼出現擾動信號。表達式如下：

若滿足條件則進入局部擾動態，繼續執行步驟2，否則跳出，并在下輪進行檢測。

2）編碼規范化處理：將尖峰信號處理取倒數，其他編碼不變。

3）計算鄰域幾何均值：根據上一步統一規范化處理后的編碼計算其幾何均值。

5）完成擾動：推出擾動計算，進入收斂計算過程。

通過擾動計算，節點將事件產生的擾動信息以類Gossip 方式傳播到全網絡中，從而讓所有的節點都能感知到該擾動，這種機制保證了本文算法4 個特性中的傳播性。系統完成一次擾動計算之后馬上就進入到收斂計算，在收斂計算過程中，節點不會再次進行擾動計算，這可以避免網絡中出現同一個事件消息多次被識別為擾動源。

2.2.2 收斂模塊

當結束擾動計算后，收斂計算將會持續多輪直到本地節點進入到局部收斂態。如果將擾動計算過程視作擾動產生的全局信息的傳輸過程，那么收斂計算則可以看作對該信息的存儲過程。收斂計算的具體步驟如下：

1）編碼規范化處理：計算鄰域幾何均值，過程同擾動模塊。

2）編碼更新：如果編碼的差值小于閾值?，則進入到局部收斂狀態，編碼無須更新，否則更新編碼。

3）狀態更新：如果當前狀態被評估為非局部收斂狀態，那么不退出當前收斂計算過程，下一輪將重復步驟1～步驟3。如果當前已經是局部收斂狀態，那么再評估連續處于收斂狀態的輪數是否大于D（D為網絡直徑），如果大于則進入到穩定態，否則節點將依然處于局部收斂狀態并將繼續執行上述算法，直到滿足穩定態條件退出當前計算過程。節點狀態變化過程如圖2 所示。

圖2 節點狀態變化過程Fig.2 Process of node status change

2.2.3 整體計算模型

在網絡正式運行前，需要完成節點的初始化工作，此時節點處于局部收斂狀態。節點之間通過消息同步時鐘，節點持續在每輪時鐘下監測鄰居節點的活躍性，執行擾動模塊的算法過程。當檢測到擾動信號時，執行收斂模塊過程，2 個模塊和4 種狀態的交替構成了整體算法過程，如圖3 所示。

圖3 節點的整體計算過程Fig.3 Overall calculation process of nodes

2.2.4 性質

基本性質主要有以下4 種：

1）傳遞性

定義：給定一個連通網絡G(V,E)，當完成初始化工作后，若網絡某處發生拓撲事件變化，則時空編碼構造的算法過程會將該事件傳遞到網絡所有節點下，使得節點由全局穩定態進入局部擾動態，進而完成計算編碼過程。

證明：假設拓撲事件發生時與事件源所在節點為Vi，其所關聯的鄰居節點Ni一定能直接檢測到事件信息并運行擾動模塊，傳遞尖峰編碼。當鄰居節點Ni產生尖峰編碼后，節點的鄰居節點將在本時鐘輪收到尖峰編碼，在下一個時鐘輪中，將由局部收斂態進入到局部擾動態。同樣地，鄰居節點也會生成尖峰編碼，并傳遞給其鄰居節點。由于給定的網絡為連通網絡，且拓撲事件不改變連通性，那么鄰居節點Ni發出的尖峰編碼將最多經歷|D| 個時鐘輪就使得所有的節點從穩定態進入局部擾動態，這里的|D|為網絡的直徑大小。也就是說，時空編碼構造過程能夠在最多|D|個時鐘輪之后將網絡中的某處發生的拓撲事件傳遞到全網所有節點，即傳遞性得證。

2）收斂性

定義：給定一個連通網絡G(V,E)，當網絡中某處產生了拓撲事件，所有節點從全局收斂態進入到局部擾動態（傳遞性），收斂性將保證網絡所有節點按照收斂模塊算法運行有限時間之后重新收斂到全局穩定態。

定理1任意節點Vi的編碼可以表示為，其中，αi是代數數，pi是素數［33］。

證明：網絡G(V,E)的某處發生了拓撲事件，節點將不斷執行收斂模塊算法，更新本地編碼值，變化的編碼值始終處在范圍（0，1）中。由定理1 可知，在第t時鐘輪，節點Vi的編碼可以表示如下：

式（10）說明，節點在執行收斂模塊算法過程中，節點的編碼值不斷遞減。而收斂模塊中當節點的編碼值小于閾值?時，編碼將保持不變，多輪之后節點進入本地收斂態。上述過程說明，節點在多輪時鐘之后將進入本地收斂態，當所有節點都進入本地收斂態后，全網狀態則進入全局收斂態。

3）因果性

定義：給定一個連通網絡G(V,E)，在相同的初始化配置和相同輸入的情況下，時空編碼的算法過程將產生相同的編碼序列。而在初始化配置不同和（或）輸入不同的情況下，算法過程將產生不同的編碼序列，即以下3 種情況：（1）相同初始條件，不同的拓撲事件原因將產生不同結果；（2）不同初始條件，相同的拓撲事件原因將產生不同結果；（3）不同初始條件，不同的拓撲事件原因產生不同結果。

定理2對于一個連通網絡G(V,E)，在某個時刻下，全局的拓撲連接矩陣表示為C，全局編碼集合表示為X。在經過一次拓撲事件后，全局拓撲連接改變為C1，對于任意兩個網絡中的節點Vi、Vj,i≠j，必然有

定理3對于一個連通網絡G(V,E)，在某時刻下，全局的拓撲連接矩陣表示為C，全局編碼集合表示為X。當經過兩次拓撲事件后，全局拓撲發生改變：

由此造成的全局網絡中各個節點的本地編碼均不相同，有：

其中：Vi、Vj為網絡中的節點，且允許i=j的情況，這種情況即相同節點在不同的拓撲結構下編碼是不同的。

證明：由以上兩個引理可以推出在相同初始配置和相同輸入情況下編碼序列相同。而不滿足任意一個條件都將使得編碼序列不同，有：（1）相同初始條件，不同的事件序列導致不同的全局編碼序列；（2）不同初始條件，相同的事件序列有不同全局編碼序列；（3）不同初始條件和不同時間序列有不同全局編碼序列，即事件原因和結果一一對應。

4）確定性

定義：在相同的網絡初始化條件下，給定系統相同的輸入，時空編碼算法過程總是到達相同的網絡狀態，產生一致的輸出結果。

證明：由時空編碼算法的數學過程可知，涉及編碼計算的函數均為單射的確定性函數。因此，給定相同的初始條件，保證節點能正確執行編碼算法的情況下，時空編碼運行的整個過程是確定的，不會有隨機因素參與并改變執行的結果。其演化過程在相空間中表現為固定的軌跡。

3 基于超越數論時空編碼的無線傳感器網絡信息存算通信一體化方法

3.1 基于無線傳感器網絡模型的編碼方法

本節提出基于非定域感知理論的時空編碼方法，將非定域感知理論的拓撲感知場景擴展到普遍的信息感知場景下，并給出數據收集與感知的具體編碼過程。

在網絡處于全局收斂的狀態下，節點或者邊的增加或者刪除會生成一個尖峰信號，尖峰信號將會被記錄在節點的本地編碼中，最終被全網所有節點感知到。這種蝴蝶效應的結果將會被反映到網絡所有的節點的本地編碼中。節點將本地編碼運行分解算法得到傳播路徑，從可以定位得到擾動源節點，實現非定域感知。如果將擾動源節點固定為兩個節點，并將其映射為0 和1，那么可以將普遍的信息映射到每個節點的本地編碼中，編碼過程如圖4 所示。如算法1 所示，將一系列事件信息以0-1 序列形式注入到網絡中，經過節點反復的收斂和傳播計算，這些信息將會被編碼存儲在網絡所有節點中。

圖4 編碼過程Fig.4 Encoding process

算法1基于非定域感知理論的混沌編碼過程

3.2 基于無線傳感器網絡模型的解碼方法

根據前文對非定域感知理論的討論可知，本文算法具有因果性和確定性，在某個時間點下產生的事件將會唯一地被記錄在網絡中各個節點的本地編碼中，并能夠唯一地被解析恢復。基于前面的編碼算法，本文提出一個基于編碼序列的解碼方案，解碼過程如圖5 所示。如算法2 所示，此方案利用基于掃描線的搜索算法定位引起上一次網絡拓撲變化的源節點，通過多次定位事件源節點來解析出源事件序列。對于節點來說，只需在解碼時執行此算法，在一般情況下只需要接受鄰居編碼并更新本地編碼即可。通過這種策略，本文將通信和存儲域上的開銷轉移到計算域上的開銷，突破了節點存儲和通信能力的限制，從而能達到持續地、實時地、非定域地感知信息。

圖5 解碼過程Fig.5 Decoding process

算法2非定域時空編碼解碼過程

4 實驗結果與分析

4.1 實驗設置

實驗使用Ubuntu 18.04 LTS 版本為操作系統，CPU 為i7-9750H，軟件環境為Java17.0.2，JVM 為HotSpotTM64 bit Server VM。實驗通過多線程模擬節點，使用線程的創建，銷毀仿真節點的加入退出的行為。節點之間的通信使用Socket 通信方式來完成，這一方案也有利于模擬實際通信過程中的丟包、重連等情況。另外，系統中的松散時鐘部分使用了基于消息的同步機制來進行模擬。實驗將網絡分為編碼輸入節點、普通節點以及在普通節點中隨機選取的節點作為解碼節點。實驗將編碼固定輸入節點表示為NODE0、NODE1，以拓撲變化事件信息源固定為編碼輸入節點的拓撲變化事件，將感知信息抽象為0-1 序列，隨機選擇要輸入的0-1 序列信息Sin=b0,b1,…,bn，其長度為n=|Sin|，bi?0,1。輸入完畢后網絡處于全局收斂狀態，此時隨機選取節點NODEr作為解碼節點，運行算法2，解碼得到序列Sout=B0,B1,…,Bm，比較Sin和Sout。改變網絡拓撲、網絡規模|S|以及輸入序列Sin的長度，檢測算法在不同場景下的表現。

4.2 結果分析

為驗證本文方法的正確性和有效性，以網絡中的拓撲變化事件作為信息源進行測試，實驗將從準確度、通信開銷、存儲開銷、計算開銷、收斂速率等方面進行評估。

1）準確度。如圖6 所示，在節點數目較多的網絡中，對于中短序列檢測準確度接近于100%，長序列檢測準確度下降。當序列長度一致時，節點數目越多的網絡，檢測度越高。對此現象可以解釋為當節點數量增加時，群體的整體存儲計算能力增強，同時對應的抗干擾能力也會增強，從而增加了信息恢復準確度。而在網絡規模確定的情況下，準確度隨著輸入序列長度增加而降低。這是由于時空編碼依賴于浮點數計算，而計算機二進制表達浮點數的精度有限，因此出現準確度下降問題。

圖6 不同網絡規模和本地編碼大小下的準確率Fig.6 Accuracy under different network sizes and local code sizes

2）通信復雜度。在本文提出的算法中，每個節點只需和m個鄰居節點通信，其通信復雜度為O(mn)，其中，m為節點平均的鄰居個數，在最好情況下為m=1。在理論的最壞情況下，如在全連接的網絡拓撲中，每個節點都和其他節點連接，最差通信復雜度為O(n2)，所以編碼消息整體通信復雜度為O(n)。然而，本文是通過將本地編碼搭載在Beacon消息上來完成鄰居節點之間的通信的，所以不會產生額外的通信開銷，從額外通信數據角度來看，本文的通信開銷為常數級。實驗中將通信次數C和通信數據包大小S的乘積來衡量通信開銷CCostc，通信包含數據輸入并存儲在網絡中的過程store，也包括數據從網絡中取出來的過程query，總的開銷表示為：CCostc=Cstore×Sstore+Cstore×Sstore。將時空編碼方法和其他WSN 存儲相關方法進行比較，包括基于分布式存儲方式使用Double Rulings（DR）［34］方法來解決數據可用性問題方法、基于分布式存儲使用糾刪碼系統RRNS 來提高數據安全性的方法［35］、基于本地存儲的Directed-Diffusion（DD）方法［36］。不同序列長度和網絡規模下通信開銷如圖7 所示。在圖7（a）中，本文方法隨著網絡規模的增長呈線形增長，這是因為在輸入序列數據較小的情況下，編碼的開銷不可忽略。而在輸入比特序列增加的情況下，發現本文方法的通信開銷逐漸逼近到了常數級別。理論上Directed-Diffusion 由于需要使用洪泛的方式獲取數據，從而產生了較高的開銷。RRNS 需要將數據切分成數據塊，并額外生成校驗數據塊，增加了額外的通信次數和數據量。相比之下，本文的方法在通信開銷方面有更好的表現。

圖7 不同序列長度和網絡規模下的通信開銷Fig.7 Communication overhead under different sequence lengths and network scales

3）存儲復雜度。本文方法中每個節點只需存儲鄰居節點發來的上輪編碼，以及節點自身的編碼，節點只需不斷利用鄰居節點的編碼計算并更新自身編碼即可。類似通信復雜度，節點的存儲開銷為O(m)，其中，m為節點的鄰居節點個數，是一個常數，所以整體存儲開銷為O(1)。

如圖8 所示，DR 方法需要將數據把副本復制到ReplicateCurve 上的節點，所以會產生大量存儲。基于糾刪碼的方法需要額外存儲校驗數據，所以會產生少量冗余（這里糾刪碼冗余度為1.33）。從實驗結果可以看出，本文方法相比其他方法有明顯的優勢。

圖8 不同序列長度和網絡規模下的存儲開銷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 拓撲結構中，對網絡中節點的平均收斂輪數進行測試，網絡中節點的收斂輪數大致呈正態分布，這從實驗的角度進一步驗證了本文算法的收斂性。實驗結果如圖9 所示，網絡中的大部分節點都能在有限時間內完成收斂計算，能夠在一定程度上應對實時性的要求。

圖9 收斂輪數及頻率Fig.9 Convergence rounds and frequency

5 結束語

為了解決無線傳感器網絡中的及時持續收集全局信息、巨大的網絡通信量與較高的時延之間的問題，本文借助網絡狀態信息和計算空間時空結構之間的數學關聯，提出在存儲、通信、計算上常數開銷的時空編碼算法，實現對拓撲變化信息的計算感知，解決通過洪泛手段收集全局信息帶來的通信開銷問題。實驗結果表明，該方法具有良好特性。后續將研究在節能、通信受限、存儲有限等場景下的優化問題，提高時空編碼方法的實用性。