《無線移動感測器最佳化部署算法研究》是依託西安電子科技大學，由沈中擔任項目負責人的面上項目。
基本介紹
- 中文名：無線移動感測器最佳化部署算法研究
- 項目類別：面上項目
- 項目負責人：沈中
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
隨機部署的無線感測器網路在覆蓋率、連通性和網路生存時間等方面都很難達到要求。提高感測器網路的連通性和覆蓋率的一種有效方法是利用移動感測器。本課題研究移動感測器的最佳化部署算法，重點研究最大化感測器網路覆蓋率、實現對目標區域多重覆蓋、修復網路分割以及增強網路抗毀性等問題。課題將在以下方面取得創新性成果：(1)提出基於二部圖匹配的移動部署算法最大化感測器網路的覆蓋率。(2)提出多重覆蓋移動部署算法的一個廣義最佳化目標，並將該問題描述成一個多步最佳化問題。結合網路流和凸最佳化的理論求解這個多步最佳化問題。(3)提出利用凹網路流描述網路分割修復問題，證明了該問題是NP難解問題。(4)提出移動一些特定的節點建立一個兩連通的網路，增強網路的抗毀性。本課題力圖從理論上解決移動感測器的最佳化部署問題，並為感測器網路的實際套用提供有效的研究成果。發表高水平論文10多篇，申請專利2項，和國際研究水平同步。
結題摘要
為了提高感測器網路的連通性和覆蓋率，本課題研究移動感測器的最佳化部署算法，取得的主要研究成果如下： （1）基於網路流和凸最佳化的理論研究多重覆蓋的移動部署問題：多重覆蓋的移動部署問題被描述成一個具有“廣義”最佳化目標的三步最佳化問題，它包含了一系列的移動感測器最優重部署問題。我們提出使用網路流和凸最佳化的方法解決此類問題，並從理論上證明了該方法是一種可以求解這個系列最佳化問題的機制。 （2）移動場景下的k連通分析：研究了節點移動對網路連通性的影響。對於一維線型拓撲結構，我們從理論上導出了網路保持k連通的充分和必要條件。基於此條件，利用矩陣分解，導出了網路是k連通的機率表達式。 （3）基於最優止步理論的數據傳輸調度：為了減少數據源節點的佇列延遲以及數據傳輸的能量消耗，定義了一個花費函式，當延遲超過上界時，將導致一個懲罰性的開銷。為了最小化單位時間的花費，使用最優止步理論求解該最佳化問題，導出了一個簡單、基於閾值的最優止步策略。 （4）利用“可移動節點”提高網路的抗毀性：通過理論分析，首先得到“可移動節點”的一個充分和必要條件，設計了一個利用局部信息確定“可移動節點”的分散式的算法，提出了一個基於最短距離的移動算法，該算法確定“可移動節點”的目的位置，使得相關的割點變成非割點，而且移動距離最短。 （5）占空比網路的快速數據收集：為了最小化數據收集時間，對於線型占空比感測器網路，我們提出了一個快速數據收集的分散式算法，並證明了當周期等於3時，該算法與最優算法的時間差的一個上界。對於一般的占空比感測器網路，我們使用動態規劃的方法研究最小延遲匯聚路由，提出了一個分散式算法，該算法能夠確定所有節點在任意時刻到匯節點的最小延遲路由。 （5） 移動節點調度修復網路分割：為了最小化傳輸信息的能量開銷，導出了連線兩個孤立塊的最優中繼位置。證明了連線多個孤立塊的移動中繼調度問題是一個NP難解問題。提出了兩個啟發式的算法。第一個啟發式算法將所有塊連線起來，形成一個連通網路。第二個啟發式算法不僅把所有塊連線起來，而且任意一個移動中繼或者網關節點的失效都不能分割修復後的網路。 我們構建了一個由30個TelosB節點組成的無線感測器試驗網路，用於驗證所提出的協定或者算法的性能。已發表和線上發表項目相關論文9篇，其中發表在SCI刊物上的論文7篇，EI刊物上的論文2篇。申請專利4項，已授權專利1項。
