基於貪心路徑的移動sink節點數據收集方法
2023-12-07 07:07:56
基於貪心路徑的移動sink節點數據收集方法
【專利摘要】本發明涉及一種移動sink的WSN和基於貪心路徑的移動sink數據收集方法。該WSN包括一個移動sink節點和兩個以上的sensor節點；該方法包括：將WSN分成若干大小均衡的簇；移動sink節點確定一條順序訪問各簇頭的貪心路徑；移動sink以確定的路徑重複訪問各簇頭節點，並收集信號；簇頭節點的信號以一跳或多跳方式通過路徑中相鄰簇頭傳遞至移動sink；在數據收集過程中採用定時器機制避免處理重複數據，降低sensor節點能耗。本發明在減少數據採集的時延同時，均衡網絡能耗，延長網絡壽命。
【專利說明】基於貪心路徑的移動S i nk節點數據收集方法
【技術領域】
[0001]本發明涉及一種無線傳感器網絡(Wireless Sensor Networks, WSN),特別是一種採用移動sink節點的WSN的數據收集方法。
【背景技術】
[0002]典型的WSN主要由大量具有感知能力的傳感器節點(sensor)和匯聚節點(sink)構成。sensor通過單跳或多跳的方式傳遞信息給sink。在sink節點固定的場合,sink節點近端的sensor由於要大量的轉發遠端sensor的信息，導致能耗遠大於遠端，形成了 「熱區」問題，縮短了 WSN的壽命。移動sink的引入很好解決了「熱區」問題:移動sink在網絡控制下，主動地訪問sensor節點收集數據，避免了 WSN能耗集中在局部區域，均衡了網絡的能耗，進而延長網絡的壽命。通常移動sink節點按照一定的路徑順序訪問各sensor節點，在sensor的通信範圍內時,sensor節點將感知信息傳給移動sink節點,但當移動sink移動周期較長時，會帶來較長的時延，不利於緊急數據的傳遞。
[0003]申請號為201110070863.2， 申請日期:為2011年3月23日的國內發明專利申請公開了一種混合sink節點WSN及其數據收集方法,採用移動sink結合固定sink節點方式。其中移動sink以能量最佳移動半徑在固定圓軌道移動收集數據包，固定sink保證實時數據的傳遞，對延時容忍型數據，sensor把它暫存其緩存區，之後通過移動sink收集或固定路由發送至固定sink，一定程度上解決了 WSN 「熱區」問題並能滿足不同類型的數據傳遞要求。但由於移動sink節點的覆蓋區域有時效性，當WSN內實時數據量較大時，主要還是通過固定路由方式，「熱區」問題並沒有根本解決。
[0004]申請號為201210053320.4， 申請日期:為2012年3月3日的國內發明專利申請公開了一種移動無線傳感器網絡sink節點的開發方法。首先對WSN分簇，然後通過最優哈密爾頓算法確定移動sink節點的訪問各簇頭飛行航跡。簇頭節點融合感知節點的數據後暫存，等收到移動sink的收集信號後再將存儲數據轉發給移動sink，完成數據收集。最優哈密爾頓路徑可以保證移動sink訪問各簇頭的總體代價最低，但完成一次遍歷收集需較長時間，對緊急型數據不能保證其實時性要求。
[0005]在WSN的實際應用中，有的信息，例如環境監測中傳感器周期性上傳的監測數據，允許一定程度延遲。而在突發情況下，例如煤礦井下環境監測中，當溫度或瓦斯濃度超標時，sensor感知的數據必須儘快上傳至監控中心，對數據採集的可靠性和實時性都有嚴格要求。如何在滿足不同類型數據傳遞需要同時又能均衡網絡節點能耗，延長網絡壽命是迫切需要研究者解決的新課題。
【發明內容】
[0006]本發明主要針對移動sink米集信號時延較大的問題,提出一種基於移動sink貪心路徑的WSN數據採集方法，在減少數據採集的時延同時，均衡網絡能耗，延長網絡壽命。
[0007]為了避免固定sink導致的「熱區」問題，本發明採用一個移動sink節點和多個sensor的組織方式；假設sensor均勻分布在所述WSN範圍內，每個sensor節點已經通過定位技術事先確定了自己的位置信息，而且可以根據通信距離大小動態調整自己的通信半徑，移動sink節點的能量不受限制，並且可以實時按照預設的路徑移動，不斷收集sensor的信號，每個sensor有唯一的標識ID。
[0008]WSN事先分成若干簇，簇內節點將感知到的信號發給簇頭節點，後者把收到信號融合處理後通過一跳或多跳方式，按照預設的路徑發送給移動sink節點。移動sink節點在採集過程中以貪心路徑依次訪問各簇頭節點並收集數據。具體步驟為:
[0009]步驟1:首先將WSN分成若干大小均衡的簇。
[0010]步驟2:移動sink節點確定一條順序訪問各簇頭的貪心路徑。
[0011]步驟3:移動sink節點將路徑信息在WSN中廣播，每個簇頭確定路徑中自己的相鄰簇頭集合，分別作為前驅集合和後繼集合，並確定自己和相鄰簇頭的通信半徑。
[0012]步驟4:移動sink以確定的路徑重複訪問各簇頭節點，並收集信號。
[0013]步驟5:簇頭節點的信號以一跳或多跳方式通過路徑中相鄰簇頭傳遞至移動
sinko
[0014]作為本發明的一種優選方案,步驟I中的分簇，WSN可以採用HEED或基於voronoi圖等均衡的分簇方法，得到簇節點數目比較接近的分簇。各簇頭節點的位置信息通過洪泛廣播方式告訴移動sink節點，這樣任意兩個簇頭之間距離可以確定，移動sink節點最終得到一個由各簇頭和簇頭之間邊組成的無向完全連通圖G。
[0015]作為本發明的另一種優選方案，步驟2中移動sink節點確定貪心路徑的過程為:
[0016]步驟201:初始化路徑隊列S為空；
[0017]步驟201:選擇G中一個最短邊，分別把兩個簇頭(隊頭和隊尾)加入路徑隊列S ；
[0018]步驟202:在圖G中選擇一個簇頭O，且O距離對頭或者隊尾簇頭最近，如果O距離原隊頭更近，把O插入隊頭之前成為新隊頭；否則插入隊尾成為新隊尾；如果有多個簇頭距離對頭和隊尾距離相同，則可以任取一個作為新隊頭。
[0019]步驟203:重複步驟202，直到所有簇頭都在路徑隊列S中為止。
[0020]作為本發明的再一種優選方案，步驟3中移動sink節點將隊列S在網絡中廣播，其廣播範圍可以覆蓋整個WSN，每個簇頭節點收到隊列S信息後，確定路徑中自己的前驅和後繼簇頭集合，並分別根據自己到前驅、後繼兩個簇頭的距離確定相應通信半徑R1，R2。隊頭和隊尾簇頭分別只確定通信半徑R2和R1。
[0021]作為本發明的再一種優選方案，為了減少移動sink節點的移動時延，步驟4中移動sink節點按路徑S序列訪問完隊尾簇頭後立即按原路返回，即以S序列的反序訪問簇頭，以此方式不斷循環訪問隊列中的簇頭，完成數據的收集。
[0022]作為本發明的再一種優選方案，在步驟5中，為了實現消息轉發，在消息中加入源簇頭ID和轉發簇頭ID兩個欄位，分別表示消息源簇頭標識和上一跳簇頭標識。源簇頭收到本簇節點感知的信號後，分別在源簇頭ID和轉發簇頭ID加入自己的ID，再以通信半徑Rl, R2的較大者對鄰居簇頭廣播，讓消息沿路徑S向兩端傳遞，儘快到達移動sink節點。
[0023]作為本發明的再一種優選方案，收到信息的簇頭通過消息的轉發簇頭ID確定消息的來源，如果消息來至前驅集合，則以R2發送至後繼簇頭，否則以Rl發送至前驅簇頭。而路徑S序列中兩端的簇頭(隊頭和隊尾)收到信號直接丟棄。[0024]作為本發明的再一種優選方案，為了避免重複信息，減小能耗，移動sink對每個簇頭分別設定相應定時器T，收到某個源簇頭的消息後啟動相應定時器T，在T時間內不再處理具有相同源簇頭ID的重複消息。
[0025]作為本發明的再一種優選方案，移動sink節點收到消息後馬上發出廣播，通知讓相關簇頭在T時間內不再傳遞消息源ID標識的消息。
[0026]作為本發明的再一種優選方案，當某個簇頭節點能量低於某個門限值，啟動簇頭選舉輪換，原簇頭將新簇頭的信息(ID，位置)等廣播給鄰居簇頭，通知它們修改自身的前驅後繼和相應通信半徑等信息。廣播的消息同樣通過在路徑S中雙向傳遞至移動sink，後者修改路徑序列並設定新簇頭的定時器，以新路徑序列繼續訪問收集數據。
[0027]如上所述，本發明中所述的貪心路徑數據採集方法，具有以下有益效果:
[0028]本發明在均衡分簇基礎上採用移動sink在貪心路逕往復移動的方式，同時簇頭節點採用雙向傳遞方式傳遞信號，最大程度減少了數據的延遲，避免了固定sink引起的「熱區」效應，均衡了網絡能耗，延長網絡壽命。
【專利附圖】
【附圖說明】
[0029]圖1為本發明中移動sink節點確定的貪心路徑及sink節點移動示意圖。
[0030]圖2為貪心路徑確定流程圖。
[0031]圖3為移動sink節點收到消息後的處理流程圖。
[0032]圖4為簇頭節點收到轉發消息後的處理流程圖。
【具體實施方式】
[0033]以下結合說明書附圖及具`體實施例進一步說明本發明的技術方案。此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。本發明還可以通過其它不同的實例實施方式進行應用。
[0034]圖1表示本發明中移動sink節點的貪心路徑示意圖，其中?表示簇頭節點，◎表示移動sink節點，〇表示一般sensor節點，所述貪心路徑即為從隊頭簇頭到隊尾簇頭的簇頭節點序列，移動sink節點不斷在隊頭和隊尾之間往復移動，並接受簇頭節點發送的消息，數據源簇頭節點發送數據前，首先確定和相鄰節點的通信半徑，其中和前驅簇頭的通信半徑記為Rl，和後繼簇頭節點的通信半徑記為R2，源簇頭節點以R1，R2較大者發送，確保消息可以分別從前驅、後繼簇頭向兩端傳遞，儘快讓移動sink節點接收。
[0035]本發明中移動sink節點事先部署在WSN網絡的中心位置，分簇完成後，各個簇頭節點通過洪泛方式廣播自己ID和位置信息，具體方式如下:每個簇頭節點在含有自身信息的幀上設定最大轉發次數M，然後廣播。收到轉發幀的簇頭節點將M減1，當M為零時停止轉發，否則繼續轉發，如果收到ID重複的轉發幀直接丟棄。經過洪泛廣播後，移動sink節點獲得所有簇頭的位置和ID，形成無向完全連通圖G，然後根據步驟2確定訪問各簇頭的貪心路徑。最大轉發次數M值與WSN規模及節點通信半徑有關，可以事先測定。
[0036]圖2表示移動節點生成貪心路徑的流程圖，本實施例中，具體包含以下步驟:
[0037]步驟S21:移動節點創建並初始化隊列S為空；
[0038]步驟S22:選擇無向圖G中的最距離短邊，分別將其頂點對應的兩個簇頭插入隊列；
[0039]步驟S23:分別在圖G中尋找距離隊列中隊頭或者隊尾最近的頂點A，如果其距離隊頭最近轉步驟S24，否則轉S25 ；
[0040]步驟S25:將A插入隊列頭成為新隊頭；
[0041]步驟S26:將A插入隊列尾成為新隊尾；
[0042]步驟S27:判斷如果圖G所有頂點都在隊列中，結束；否則轉步驟S23。
[0043]以上步驟得到的路徑序列中，隊頭和隊尾兩簇頭的實際距離可能較遠，為了減少移動時延，移動sink節點按路徑S序列訪問完隊尾簇頭後立即以路徑S序列的反序返回，以此方式不斷循環訪問隊列中的簇頭。
[0044]移動sink在移動過程中，如果收到簇頭髮送的消息，sink節點從消息中獲得消息的源簇頭ID，並廣播通知其他簇頭一段時間內停止轉發指定源簇頭ID的消息。如圖1所示，由於貪心路徑的不規則性，當簇頭X把消息轉發給前驅W時，簇頭R也在其通信範圍內，R轉發的消息可能會先到達sink節點，sink以後收到重複源簇頭ID的消息直接丟棄。而簇頭S收到移動sink的通知後不再處理簇頭X通過簇頭T、U、V的轉發來的消息。
[0045]圖3表示移動sink節點收到消息後的處理流程圖，具體包含以下步驟:
[0046]步驟S31:移動sink節點獲得消息源簇頭ID ；
[0047]步驟S32:判斷之前是否收到過該源簇頭ID的消息，如果收到過轉步驟S33 ;否則轉步驟S34 ；
[0048]步驟S33:判斷本次收到的消息是否在定時器T時間以內，如果是則結束；否則轉步驟S34 ；
[0049]步驟S34:移動sink節點啟動定時器T並發出廣播，通知所有簇頭在時段T內停止轉發該源簇頭ID的消息，結束。
[0050]移動sink的廣播幀內含有收到消息的源簇頭ID、時段T長度、T的起始時間，移動sink把時段T以內的收到消息視為重複消息，之後則為簇頭產生的新消息。時段T的長度與WSN規模、簇頭數量、sink移動速度有關。
[0051]圖4表示簇頭節點收到轉發消息後的處理流程圖，具體包含以下步驟:
[0052]步驟S41:如果本簇頭是路徑中隊頭或隊尾簇頭，結束；否則轉步驟S42 ；
[0053]步驟S42:簇頭節點獲得消息的源簇頭ID ；
[0054]步驟S43:如果已收到移動sink通知停止轉發對應源簇頭ID的消息，轉步驟S44 ；否則轉步驟S45:
[0055]步驟S44:如果收到移動sink的停止轉發消息在時段T內，結束；否則轉步驟S45 ；
[0056]步驟S45:獲得消息的轉發ID，並將轉發ID欄位修改為簇頭節點自身ID ；
[0057]步驟S46:如果消息的轉發ID來自前驅集合，用通信半徑R2傳給後繼簇頭，結束；否則轉步驟S47:
[0058]步驟S47:用通信半徑Rl傳給前驅簇頭，結束。
[0059]以上所述僅為本發明的優選實施例，並非限制本發明的專利範圍，凡利用本發明說明書及附圖所做的等效結構或者流程變換，均包括在本發明的保護範圍內。
【權利要求】
1.一種基於移動sink節點貪心路徑的WSN數據採集方法，採用一個移動sink節點和多個sensor的組織方式,其特徵在於，sensor均勻分布在所述WSN範圍內； 所述移動sink節點按照預設的路徑移動，不斷收集sensor的信號； 所述sensor節點通過簇頭一跳或多跳的方式，按照預設的路徑發給所述移動sink節點。
2.根據權利要求1所述基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink節點在採集過程中以貪心路徑依次訪問各簇頭節點並收集數據。所述方法具體步驟為: 將所述WSN分成若干大小均衡的簇； 所述移動sink節點確定一條順序訪問各簇頭的貪心路徑； 所述移動sink節點將路徑信息在所述WSN中廣播，每個簇頭確定路徑中自己的相鄰簇頭集合，分別作為前驅集合和後繼集合，並確定自己和相鄰簇頭的通信半徑； 所述移動sink以確定的路徑重複訪問各簇頭節點，並收集信號； 簇頭節點的信號以一跳或多跳方式通過路徑中相鄰簇頭傳遞至所述移動sink。
3.根據權利要求1或2所述的WSN，其特徵在於，所述WSN採用HEED或基於voronoi圖等均衡的分簇方法，得到簇節點數目比較接近的分簇；各簇頭節點的位置信息通過洪泛廣播方式告訴所述移動sink節點，所述移動sink節點最終得到一個由各簇頭和簇頭之間邊組成的無向完全連通圖G。
4.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink節點確定貪心路徑的步驟為: 初始化路徑隊列S為空； 選擇無向完全連通圖G中一個最短邊，分別把兩個簇頭(隊頭和隊尾)加入路徑隊列S ； 在圖G中選擇一個簇頭O，且0距離對頭或者隊尾簇頭最近，如果0距離原隊頭更近，把0插入隊頭之前成為新隊頭；否則插入隊尾成為新隊尾；如果有多個簇頭距離對頭和隊尾距離相同，則可以任取一個作為新隊頭； 重複上一步驟，直到所有簇頭都在路徑隊列S中為止。
5.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink節點確定貪心隊列S以後將隊列S在網絡中廣播，其廣播範圍可以覆蓋整個WSN，每個簇頭節點收到隊列S信息後，確定路徑中自己的前驅和後繼簇頭集合，並分別根據自己到前驅、後繼兩個簇頭的距離確定相應通信半徑Rl，R2。隊頭和隊尾簇頭分別只確定通信半徑R2和Rl。
6.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink節點按路徑S序列訪問完隊尾簇頭後立即以S序列的反序返回訪問簇頭，以此方式不斷循環訪問隊列中的簇頭，完成數據的收集。
7.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述傳遞的消息中包括源簇頭ID和轉發簇頭ID兩個欄位，分別表示消息源簇頭標識和上一跳簇頭標識。源簇頭收到本簇節點感知的信號後，分別在源簇頭ID和轉發簇頭ID加入自己的ID，再以通信半徑R1，R2的較大者對鄰居簇頭廣播，讓消息沿路徑S向兩端傳遞，儘快到達移動sink節點。
8.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，收到信息的簇頭通過消息的轉發簇頭ID確定消息的來源，如果消息來至前驅集合，則以R2發送至後繼簇頭，否則以Rl發送至前驅簇頭。而路徑S序列中兩端的簇頭(隊頭和隊尾)收到信號直接丟棄。
9.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink對每個簇頭分別設定相應定時器T，收到某個源簇頭的消息後啟動相應定時器T，在T時間內不再處理具有相同源簇頭ID的重複消息。
10.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，所述移動sink節點收到消息後馬上發出廣播，通知相關簇頭在時間T內不再傳遞消息源ID標識的消息。
11.根據權利要求2所述的基於移動sink節點貪心路徑的WSN數據採集方法，其特徵在於，當某個簇頭節點能量低於某個門限值，啟動簇頭選舉輪換，原簇頭將新簇頭的信息(ID，位置)等廣播給鄰居簇頭，通知它們修改自身的前驅後繼和相應通信半徑等信息。廣播的消息同樣通過在路徑S中雙向傳遞至所述移動sink，後者修改路徑序列並設定新簇頭的定時器，以新 路徑序列繼續訪問收集數據。
【文檔編號】H04W84/18GK103619033SQ201310646561
【公開日】2014年3月5日 申請日期:2013年12月4日 優先權日:2013年12月4日
【發明者】胡長俊, 李鑫, 韓迎鴿, 袁樹傑 申請人:安徽理工大學