一種基於移動節點的無線傳感執行網絡覆蓋方法
2023-05-30 00:34:41
專利名稱：一種基於移動節點的無線傳感執行網絡覆蓋方法
一種基於移動節點的無線傳感執行網絡覆蓋方法技術領域
本發明屬於無線傳感執行網絡技術和智能計算兩大領域，具體涉及一種基於移動節點的無線傳感執行網絡覆蓋方法。
背景技術：
無線傳感執行網絡的組網方式介於機器人網絡和靜態無線傳感器網絡之間，一部分節點是具有信息採集能力的傳感器節點，另外的節點是具有信息匯聚和中繼、信息融合、 信息解釋執行等能力的執行節點，這種由不對等節點組成的網絡更適用於實際的應用環境，在網絡能力和代價之間取得權衡。
自無線傳感執行網絡的概念提出以來[I]，相關技術多擬照傳統傳感器網絡的應用環境，針對靜態環境下無線傳感執行網絡的通信和協作方式。然而，對於空間監視巡航、 環境汙染控制、應急安全處理等多方面的迫切應用需求，多類傳感信息平臺往往在大尺度空間進行分布，並且信息數量和採集地點隨時間而改變，所形成的「傳感信息簇」相隔甚遠或者由於基礎通信設施損壞無法覆蓋整個信息空間，而相應應用往往需要綜合多個「傳感信息簇」的信息從而作出決策和執行相應的命令，因此，傳感執行網絡需要利用能力強的執行節點滿足動態的網絡互聯需求。該類網絡具有承載業務對網絡傳輸可靠性和實時性要求高、執行節點可移動和節點非對稱的特點。
執行節點的移動性和強大計算能力有利於動態環境下互聯「傳感信息簇」，但針對大尺度空間信息分布的相關應用，仍然存在以下難點
( I)難以形成穩定的網絡互聯骨幹。傳感信息分布不均勻，並且動態變化，很難形成類似最小支配集的穩定的互聯骨幹，因此需要網絡具有自組裝的能力。
(2)難以在各節點上規劃全局一致的互聯拓撲。執行節點感知信息受限，不可能獲取所有「傳感信息簇」的全部精確信息，因而不能效法網際網路中的互聯方式，難以在互聯節點上進行全局一致的網絡拓撲規劃，只能依靠各執行節點的分布式智能獲得相應的網絡互聯結構。
國外研究者陸續針對無線傳感執行網絡的協作機制、通信協議、QoS保證、信息解析等多方面開展研究，取得了一系列研究成果。國內不少高校和研究所也對無線傳感執行網絡展開了研究國防科技大學並行與分布式國家重點實驗室率先開始對無線傳感反應網絡進行研究；浙江大學網絡傳感與控制研究組重點研究了無線傳感執行網絡的分布式協調控制；復旦大學鍾亦平教授領導的研究小組主要針對無線傳感執行網絡的密鑰管理展開探索；西安電子科技大學應用數學系的馮海林副教授則對無線傳感執行網絡的容錯拓撲控制機制進行理論研究。
目前，有關無線傳感執行網絡覆蓋的研究主要集中在以下來兩個方面
(I)執行節點的有效部署——在網絡連通的情況下獲得最大化的覆蓋範圍。 KemalAkkaya[2]等人在考慮最大化覆蓋面積和最小化延遲雙重目標下,提出了先部署執行節點形成簇，後調整其位置最小化延遲的經典策略；後又考慮節點移動性，在此基礎上提出了一種分布式的部署方法，以在保持連接的情況下最大化覆蓋面積[3]。Ka. Selvaradjou 在能量、資源、實時性約束的環境下，以最小化執行節點的移動距離為目標，採用混合整數非線性規劃，解決事件分配問題，使所有事件可以被相應執行節點收集[4]。Krishnakumar 則在其論文[5]中討論了在稀疏網絡中，如何規劃一個執行節點的移動路線，變相網際網路中的傳感節點。
(2)網絡容錯機制——網絡失效時及時進行路徑恢復。文獻[6-7]考慮已被連接的傳感執行網絡，當關鍵割點失效時，以最小化移動距離為目標，通過分層次移動執行節點， 替代失效的割點。文獻[8]則針對機器人網絡，在2連通網絡的基礎上，討論失效後的執行節點的移動方法，使路徑得到迅速恢復；文獻[9]則討論了該方法的具體分布式實現方式。
F. Senel和K. Akkaya[10_ll]的方法與本發明類似，探討網絡分割情況下基於移動執行節點的無線傳感執行網絡的覆蓋問題。但其研究單純從簇內執行節點的最小支撐集部署和層次化移動角度出發，在穩定網絡拓撲基礎上考慮網絡連通性問題，並沒有考慮網絡的冗餘性和有效性。目前，無線傳感執行網絡技術從單純的靜態拓撲控制轉向利用節點移動性保證網絡的連通性，從集中式的網絡規劃轉向利用分布式局部規劃獲得全局網絡的連通。然而，無論是執行節點的有效部署還是網絡容錯機制，現有的技術都是單純從拓撲連通性的角度出發，而未考慮到信息分布的不均勻和動態性，從而在實際應用中無法滿足信息傳輸的可靠性和實時性需求。
相應參考文獻
[I]Ian F. Akyildiz, Ismail H. Kasimoglu, Wireless Sensor and Actor Network s: ResearchChallenges，Journal on Ad Hoc Networks, 2004, Vol. 2, No. 4, pp. 351-367
[2]Kemal Akkayaj Mohamed Younisj COLA:A Coverage and Latency aware Actor Placement forWireless Sensor and Actor Networks, in Proceedings of IEEE 64th Vehicular TechnologyConference，Sept. 25-28，2006，pp:25-28
[3]K. AkkayajM.Younisj Coverage-aware and Connectivity-constrained Actor Positioning inWireless Sensor and Actor Networks, in Proceedings of IEEE International Conference onPerformance，Computing and Communications, New Orleans,LA, April 2007，pp:281-288
[4]Ka. Selvaradjou，M. Dhanaraj，C. Siva Ram Murthy, Energy Efficient Assignment of Events inWireless Sensor and Mobile Actor Networks, in Proceedings of IEEE International Conferenceon Networks, Sept. 2006, Vol. 2, pp:1-6
[5]Sita Srinivasaraghavan Krishnakumarj Intelligent Actor Mobility in Wireless Sensor andActor Networks, dissertation, Aug. 2008, Georgia Institute of Technology
[6] A. Abbasij K. Akkayaj M. Younisj A distributed connectivity restoration algorithm in wirelesssensor and actor networks, in Proceedings of IEEE Local Computer Networks, Dublin, Ireland, October 15-18，2007，pp:496-503
[7]K. Akkayaj A. Thimmapuramj F. Senelj S. Uludagj Distributed recovery of actor failures inwireless sensor and actor networks, in Proceedings of IEEE Wireless Communication andNetworking Conference, Las Vegas, NV, April42008，pp:2480-2485
[8]B.Basuj J. Redij Movement control algorithms for realization of fault-tolerant ad hoc robotnetworks, IEEE Networks, July-August, 2004, Vol. 18, No. 4 ，pp:36-44
[9] S. Das，H. Liuj A. Kamathj A. Nayakj I. Stojmenovicj Localized movement control for faulttolerance of mobile robot networks, in Proceedings of the First IFIP International Conferenceon Wireless Sensor and Actor Networks, Albacetej Sp ain，Sept. 2007，pp: 1-12
[10]F. Senelj K. Akkayaj M. Younisj An efficient mechanism for establishing connectivity inwireless sensor and actor networks, in Proceedings of IEEE Globe com, Washington, DC, Nov. 26-30，2007，pp: 1129-1133
[II]Kernal Akkayaj Fatih Senelj Detecting and Connecting Disjoint Sub-networks in WirelessSensor and Actor Networks,Journal of Ad hoc Networks, Feb. 4，2009發明內容
為解決現有技術缺陷，本發明提出一種能同時滿足冗餘結構和路徑儘可能短兩個要求，基於移動節點的無線傳感執行網絡覆蓋方法。
本發明的技術方案為一種基於移動節點的無線傳感執行網絡覆蓋方法，包括以下步驟
步驟一、無線傳感執行網絡中的各傳感信息簇中的執行節點選舉產生領導執行節佔.
步驟二、各領導執行節點獲取所屬傳感信息簇的信息量；
步驟三、各領導執行節點估計無線傳感執行網絡中的其它各傳感信息簇的位置， 並將其它各傳感信息簇的信息量設為固定值E ;
步驟四、假設傳感信息簇的數量為N，每個傳感信息簇由領導執行節點執行如下操作分配各執行節點的初始化移動方向，
如果某傳感信息簇中執行節點的數目η > N-I，將其它N-I個傳感信息簇的方向各分配為一個執行節點的初始化移動方向，剩餘的η-Ν+1個執行節點的初始化移動方向平分其它N-I個傳感信息簇所形成的扇形區域角度；
如果某傳感信息簇中執行節點的數目η < N-I，這η個執行節點的初始化移動方向直接平分其它N-I個傳感信息簇所形成的扇形區域角度；
步驟五、在保證與傳感信息簇內其他傳感節點和執行節點連通的情況下，各執行節點沿初始化移動方向進行移動，直到與另外傳感信息簇的傳感節點或者執行節點在相互之間的通信範圍內；
對於任意一個移動的執行節點，
如果該執行節點即將與所屬傳感信息簇的連通斷開，那麼停止移動，並標記為暫停節點，通知所屬傳感信息簇的領導執行節點；
如果該執行節點的通信範圍內新增了其它傳感信息簇的傳感節點或者執行節點成為新的鄰居節點，那麼該執行節點更新所在傳感信息簇的剩餘信息量，與新的鄰居節點交互各自所在傳感信息簇的剩餘信息量，並判斷新的鄰居節點所在傳感信息簇的剩餘信息量是否為0，是則將該執行節點標記為冗餘節點，該執行節點將剩餘信息量連同自身的位置信息匯報給本簇的領導執行節點；否則執行節點制定自身的移動方向和移動速度策略繼續移動；
對於領導執行節點，
每隔T時間，分析所屬傳感信息簇的執行節點和其它傳感信息簇的鄰接關係，當存在暫停節點，將冗餘節點沿暫停節點路線方向繼續移動；
每隔3T時間，分析有無暫停節點，如果沒有則結束。
而且，執行節點制定自身的移動方向和移動速度策略的實現方式如下，
設該執行節點為Ni,若執行節點Ni的當前運動角度處於無線傳感執行網絡中的其它兩個相鄰傳感信息簇所形成的扇形區域角度之間，在收到這兩個相鄰傳感信息簇的信息量更新消息e/或者 /+1之後按照如下方式更新節點運動速度和角度，
如果收到的信息量更新消息為0，那麼執行節點Ni停止運動，並標記為冗餘節點， 通知執行節點Ni所在傳感信息簇中的領導執行節點；
否則，相應地更新運動速度V = U或者<其中α為常e/ +Ie/ +1數，t為節點運動的時間，Vi為當前運動速度；當Vi' ( O時,節點停止運動。
本發明利用執行節點移動性解決分離的「傳感信息簇」的互聯問題，突破了靜態環境下集中式部署執行節點方案的缺陷，部署結果滿足信息分布的不均勻和動態性；模擬多頭絨泡菌的生長過程，解決無線傳感執行網絡的互聯問題，採用該方法自組裝形成的網絡互聯結構，能夠同時保證信息傳輸的可靠性和實時性。
圖I是本發明實施例動節點自組織優化無線傳感執行網絡覆蓋的流程圖。
圖2是本發明實施例領導執行節點選舉的流程圖。
圖3是本發明實施例剩餘信息量更新的流程圖。
具體實施方式
以下結合附圖和實施例詳細說明本發明技術方案。
本發明實施例根據無線傳感執行網絡的信息分布狀況，利用節點移動性模擬多頭絨泡菌的生長特性，逐步演化生成互聯多個「傳感信息簇」的網絡結構，保持網絡覆蓋的冗餘性和有效性，以滿足業務對網絡傳輸可靠性和實時性要求。多頭絨泡菌的有關實驗表明該真菌可以演化形成滿足冗餘路徑和路徑儘可能短兩個要求的網狀結構。該網狀結構非常適合於解決無線傳感執行網絡的覆蓋問題。將無線傳感執行網絡比照多頭絨泡菌的變形體「傳感信息簇」類似於營養物質，路徑帶寬類似於管狀菌絲的直徑，簇內信息越多，需要的傳輸帶寬也越大；當有另外的路徑和該「傳感信息簇」相連時，由於分流作用，所需要的帶寬將減小，類似於營養物質的減少將減緩管狀菌絲的生長。
為便於理解起見，提供以下理論基礎說明
生物個體或者單個細胞組織表現出無序性，然而其群體(或者整個生物體)往往表現出有序性，該現象被稱為「湧現」。T. Nakagaki等人在對多頭絨泡菌(一種特殊的變形蟲) 的研究中，發現該類真菌也具有以上特點，在營養物質多點分布的培養液中，多頭絨泡菌可以通過自組裝形成網狀結構，這種網狀結構是Steiner最小生成樹和環的混合物，使營養物質分布點之間既有較短的通路也有冗餘的路徑，該網絡結構符合大尺度空間上的無線傳感執行網絡互聯需求。根據實驗結果，多頭絨泡菌的這種生長特性滿足以下的數學模型。
假設節點i和j為營養物質節點，節點上的壓力分別為Pi和Pp這兩個節點由長度為Lu、半徑為的菌絲相連，營養物質的粘性為ξ。那麼，菌絲內的營養物質流量滿足以下等式 Dij
my .其中，Di1為該管狀菌絲的導流率(Pi-Pi)(!)
Dij 二(2)H
等式
對於多頭絨泡菌，管狀菌絲的半徑隨營養物質流量Q的變化而改變，Dij滿足以下 ODdt其中，f (O)是滿足f (O) = O的單調增函數；a是一個正常數，以保證流量Q為零時菌絲會消退，t表示時間。
本發明將無線傳感執行網絡比照多頭絨泡菌的變形體傳感信息簇類似於營養物質，路徑帶寬類似於管狀菌絲的半徑，簇內信息越多，需要的傳輸帶寬也越大；當有另外的路徑和該傳感信息簇相連時，由於分流作用，所需要的帶寬將減小，類似於營養物質的減少將減緩管狀菌絲的生長。為便於說明，傳感信息簇也簡稱信息簇。那麼對於信息較多的簇， 需要更多的執行節點與其相連，才能分流簇內的信息；執行節點的個數類似管狀菌絲的半徑，需要能夠越多越快地與該信息簇進行互聯。
實施例的前提條件和術語說明如下
前提條件
(I)無線傳感執行網絡由多個分割的信息簇組成，每個信息簇由多個傳感節點和少數執行節點組成。
(2)各信息簇內的傳感節點和執行節點形成一個連通的子網。
(3)各信息簇內的執行節點相對於傳感節點具有移動能力和較強的計算能力，能量充足，攜帶GPS，能感知地理位置信息。
(4)初始化階段，各信息簇內的位置估計誤差在30%以內。
術語說明
(I)各信息簇的信息量是指單位時間內該信息簇內所有傳感節點所採集的信息量之和；各信息簇的剩餘信息量是指由已與其它信息簇相連通的執行節點分流後所剩餘的信息量。
(2)各信息簇的位置信息用極坐標G(d，Θ )表示。該極坐標的極點O為本信息簇領導執行節點初始位置點，極軸Ox為向正東方向所引的射線。d為信息簇的重心點P到極點之間的阿基米德距離；Θ為從Ox到OP的逆時針方向角度。
具體實施時，可以採用軟體技術實現本發明技術方案所提供流程的自動運行。如圖I所示，實施例的實現過程如下
步驟一、無線傳感執行網絡中的各傳感信息簇中的執行節點選舉產生領導執行節
領導執行節點選舉的流程如圖2所示
對於各傳感信息簇中的執行節點，如果未獲知領導執行節點，則採用定向擴散路由的方式泛洪一個領導執行節點請求消息，消息中攜帶請求節點的ID，並設定超時時間T1 ； 其他執行節點在收到領導執行節點請求消息後，如果已知領導執行節點，則返回一個應答消息給請求執行節點，並停止泛洪領導執行節點請求消息，如果也未獲知領導執行節點(那麼該執行節點也必然設定了超時時間T1),則比較請求節點和自身的ID，如果自身ID較小， 則記錄該請求執行節點的ID。在收到領導執行節點應答消息後，如果自身是應答消息的目的節點，則記錄領導執行節點，否則轉發該應答消息；如果在T1時間內，請求執行節點未收到領導執行節點返回的應答消息，則比較所記錄的所有執行節點的ID，如果自身的ID最小，那麼將自身作為領導執行節點，並且泛洪一個領導執行節點應答消息，通知其它執行節點將自己作為領導執行節點。
步驟二、各領導執行節點獲取所屬傳感信息簇的信息量。
實施例中領導執行節點採用定向擴散路由的方式泛洪一個信息量請求消息，傳感節點在收到信息量請求消息以後，將信息量返回給領導執行節點，領導執行節點計算本信息簇的信息量e,並且記本簇的剩餘信息量e^e。
步驟三、各領導執行節點估計無線傳感執行網絡中的其它各傳感信息簇的位置， 並將其它各傳感信息簇的信息量設為固定值E。
各信息簇中的領導執行節點根據已知信息估計其它傳感信息簇的位置，設第k個傳感信息簇的中的領導執行節點估計第i個傳感信息簇的位置記為GiWi, Θ J，記其它所有傳感信息簇的所形成的最大夾角為朽=1 1呲處i、j的取值為I，2，. . . N-I, 且滿足i古j，i古k，j古k ;其它各傳感信息簇的信息量都記為E，如第i個傳感信息簇的信息量t =I E為常數。
步驟四、各信息簇中的領導執行節點計算各執行節點的初始運動角度
假設傳感信息簇的數量為N，對於每個傳感信息簇，如果執行節點的數目為n，執行節點用N^N2......Nn表示；
如果η > N-I，對其它N_1個傳感信息簇的方向各分配為一個執行節點的初始化移動方向，剩餘的η-Ν+1個執行節點的初始化移動方向平分其它N-I個傳感信息簇所形成的扇形區域角度實施例中執行節點NpN2......Nim將以角度Ii= Θ i，i = 1，"·，Ν-1運動， 執行節點 Nn、Nn+1......Nn 以角度
權利要求
1.一種基於移動節點的無線傳感執行網絡覆蓋方法，其特徵在於，包括以下步驟 步驟一、無線傳感執行網絡中的各傳感信息簇中的執行節點選舉產生領導執行節點； 步驟二、各領導執行節點獲取所屬傳感信息簇的信息量；步驟三、各領導執行節點估計無線傳感執行網絡中的其它各傳感信息簇的位置，並將其它各傳感信息簇的信息量設為固定值E ;步驟四、假設傳感信息簇的數量為N，每個傳感信息簇由領導執行節點執行如下操作分配各執行節點的初始化移動方向，如果某傳感信息簇中執行節點的數目η 3N-1，將其它N-I個傳感信息簇的方向各分配為一個執行節點的初始化移動方向，剩餘的η-Ν+1個執行節點的初始化移動方向平分其它 N-I個傳感信息簇所形成的扇形區域角度；如果某傳感信息簇中執行節點的數目η <Ν-1，這η個執行節點的初始化移動方向直接平分其它N-I個傳感信息簇所形成的扇形區域角度；步驟五、在保證與傳感信息簇內其他傳感節點和執行節點連通的情況下，各執行節點沿初始化移動方向進行移動，直到與另外傳感信息簇的傳感節點或者執行節點在相互之間的通信範圍內；對於任意一個移動的執行節點，如果該執行節點即將與所屬傳感信息簇的連通斷開，那麼停止移動，並標記為暫停節點，通知所屬傳感信息簇的領導執行節點；如果該執行節點的通信範圍內新增了其它傳感信息簇的傳感節點或者執行節點成為新的鄰居節點，那麼該執行節點更新所在傳感信息簇的剩餘信息量，與新的鄰居節點交互各自所在傳感信息簇的剩餘信息量，並判斷新的鄰居節點所在傳感信息簇的剩餘信息量是否為O，是則將該執行節點標記為冗餘節點，該執行節點將剩餘信息量連同自身的位置信息匯報給本簇的領導執行節點；否則執行節點制定自身的移動方向和移動速度策略繼續移動；對於領導執行節點，每隔T時間，分析所屬傳感信息簇的執行節點和其它傳感信息簇的鄰接關係，當存在暫停節點，將冗餘節點沿暫停節點路線方向繼續移動；每隔3Τ時間，分析有無暫停節點，如果沒有則結束。
2.基於權利要求I所述的一種基於移動節點的無線傳感執行網絡覆蓋方法，其特徵在於執行節點制定自身的移動方向和移動速度策略的實現方式如下，設該執行節點為Ni,若執行節點Ni的當前運動角度處於無線傳感執行網絡中的其它兩個相鄰傳感信息簇所形成的扇形區域角度之間，在收到這兩個相鄰傳感信息簇的信息量更新消息d或者V 後按照如下方式更新節點運動速度和角度，如果收到的信息量更新消息為O，那麼執行節點Ni停止運動，並標記為冗餘節點，通知執行節點Ni所在傳感信息簇中的領導執行節點；否則，相應地更新運動速度V =<或者，其中α為常數，te/ +1e； +1為節點運動的時間，Vi為當前運動速度；當Vi' ^ O時,節點停止運動。
全文摘要
本發明提出一種基於移動節點的無線傳感執行網絡覆蓋方法，利用執行節點移動性解決分離的「傳感信息簇」的互聯問題，突破了靜態環境下集中式部署執行節點方案的缺陷，部署結果滿足信息分布的不均勻和動態性；模擬多頭絨泡菌的生長過程，解決無線傳感執行網絡的互聯問題，採用該方法自組裝形成的網絡互聯結構，能夠同時保證信息傳輸的可靠性和實時性。
文檔編號H04W84/18GK102984713SQ20121049862
公開日2013年3月20日 申請日期2012年11月29日 優先權日2012年11月29日
發明者吳靜, 楊劍鋒, 郭成城, 周建國, 江昊 申請人:武漢大學