[發明專利]一種采用優化的最近鄰算法的移動節點調度方法

在審

• 申請號: 201710340082.8
• 申請日: 2017-05-15
• 公開（公告）號: CN107172681A
• 公開（公告）日: 2017-09-15
• 發明（設計）人: 謝光前;唐學忠;張建兵
• 申請（專利權）人: 常州工學院
• 主分類號: H04W40/32
• 分類號: H04W40/32;H04W52/02;H04W84/18
• 代理公司: 南京知識律師事務所32207
• 代理人: 高桂珍

技術領域

本發明涉及一種采用優化的最近鄰算法的移動節點調度方法，屬于無線傳感器網絡技術領域。

背景技術

在無線傳感器網絡中，傳感器節點的能量持續供給受到限制，因而如何能量有效性的利用節點能量，從而最大化網絡系統的生存期已成為一項重要的研究課題。為了最大化網絡系統的生存期，其中之一方法是利用層次性的分簇路由算法。根據分簇算法，網絡系統中的傳感器節點被分為簇頭和簇內成員這兩類節點。簇的劃分是基于傳感器節點間的距離，因而簇頭的能耗是遠大于簇內成員的能耗。利用節點的移動性，可大大提高網絡系統的生存期。基于移動節點的分簇路由算法，可大大減少每一輪簇頭節點的能量消耗，因通信距離與節點的能量消耗成指數關系，而傳感器節點最大的耗能是通信模塊的耗能。當移動節點移動到簇頭位置，其與簇頭的通信距離為0，這樣可極大減少簇頭節點的能量消耗。利用移動節點來延長網絡系統的生存期，必然會涉及到移動節點的調度問題，也就是如何合理的選擇移動節點的移動路徑。

發明內容

本發明的目的是克服現有技術中存在的不足，提出了一種采用優化的最近鄰算法的移動節點調度方法，實現了移動節點的合理調度，從而最終延長了網絡系統的生存期。

按照本發明提供的技術方案，所述一種采用優化的最近鄰算法的移動節點調度方法包括以下步驟：

一種采用優化的最近鄰算法的移動節點調度方法，包括如下步驟：

步驟1：對網絡系統中的傳感器節點進行簇的劃分，網絡系統中的傳感器節點被分為簇頭和簇內成員這兩類節點；

步驟2：采用基于移動節點的分簇路由算法，利用移動節點移動到簇頭位置，收集簇頭節點采集的數據信息，并最終通過移動節點將這些數據信息傳遞給基站；

步驟3：利用優化的最近鄰算法，得到移動節點的移動路徑，移動節點按此路徑移動，最終實現移動節點的合理調度。

進一步，所述步驟1，利用分簇路由算法，將無線傳感器網絡中的傳感器節點分成簇頭和簇內成員這兩類節點，所述簇頭收集同一簇中簇內成員采集的現場信息，并對這些收集的信息進行相應的數據融合。

進一步，所述步驟2，移動節點移動到簇頭位置收集相應的數據信息，每一輪簇頭節點位置也是移動節點停留點位置，因而移動節點移動路徑必包含停留點位置、起始位置和結束位置；所述移動節點的起始位置和結束位置相同，都位于基站位置。

進一步，所述步驟3，利用優化的最近鄰算法，求得包含所有簇頭位置和移動節點初始位置的最小權的Hamilton回路，最終得到移動節點的移動路徑，移動節點按此路徑移動，實現移動節點的調度，輸出此網絡系統調度的最短移動路徑。

進一步，步驟1中，在簇的建立階段，每一輪簇頭的選舉過程為：各傳感器節點首先產生一個隨機數，隨機數的范圍為[0,1]；然后用設定的閾值T與這些隨機數進行比較，決定哪些節點成為簇頭；節點成為簇頭的條件為產生的隨機數小于閾值T(m)，相應的其他的傳感器節點成為簇內成員。

進一步，步驟2中，移動節點從起始位置出發，需通過并且僅通過一次簇頭位置，當通過簇頭位置時收集其相應的數據信息，最終回到初始位置，也就是基站位置。

進一步，步驟3具體包括：

步驟3-1：選取網絡系統基站位置s₀作為起點，找一條與s₀關聯且權值最小的一條邊e₁，e₁還和另外一個頂點相連，把此頂點記為s₁，可得一條路s₀s₁；

步驟3-2：假定已選出路s₀s₁Ls_i，從剩下的頂點選取一個與s_i最近的節點，令其為s_i+1，可得路s₀s₁Ls_is_i+1；

步驟3-3：如果i+1＜n-1，則令i←i+1返回步驟3-2；否則，記C＝s₀s₁Ls_is_i+1Ls_ns₀，其就為一個Hamilton回路，即得問題的近似解；