《無線感測器網路中最優路由樹的構造算法研究》是依託南京航空航天大學，由朱小軍擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：無線感測器網路中最優路由樹的構造算法研究
- 項目類別：青年科學基金項目
- 項目負責人：朱小軍
- 依託單位：南京航空航天大學
項目摘要,結題摘要,
項目摘要
數據收集是感測網套用的一項基本操作。如何為數據收集設計高效的路由樹來延長感測網生存時間是一個關鍵問題。然而，最優路由樹問題已被證明是NP難問題。目前，針對此問題的算法以啟發式算法為主，缺少最壞情況下的理論保證或理論保證較弱，研究者只能通過(模擬)實驗對算法進行評估，制約了對路由樹問題的進一步理解和解決。本項目研究最優路由樹的構造算法與理論，具體包含數據融合感測網的最優路由樹問題、非數據融合感測網的最優路由樹問題和新型能源感測網的最優路由樹問題。對每個問題，分析最優路由樹問題的不可近似比，提出時間複雜度更低、近似比接近理論上界的近似算法，並設計具有更低(指數)時間複雜度的精確算法。我們將結合理論推導和實驗論證的方法來驗證算法的性能。本項目的研究成果將加深對路由樹構造問題的理解，為路由結構設計提供理論指導。力爭在國際期刊或會議上發表高質量論文6-8篇，其中至少包含4篇CCF B類以上論文。
結題摘要
本項目對無線感測器網路的最優路由樹問題從難度分析、近似算法設計和精確算法設計三個方面開展了研究。突出創新之處包括：(1)提出了一種能夠與理論不可近似比匹配的近似算法，不但證明了不可近似比已不可改進，而且提出的近似算法在套用到傳統的度限制生成樹和最小度生成樹問題中時，具有更低的時間複雜度；(2)提出了最壞情況下時間複雜度為O*(2^n)的精確算法，回答了一個長期懸而未決的難題；(3)提出了在實際網路中運行速度更快的精確算法，能夠為中等規模無線感測器網路尋找到最優路由樹；(4)將最優路由樹的研究成果套用到了軟體定義網路及內容中心網路中，證明了一系列難度結論。本項目的研究推動了對最優路由樹問題的理解，具有重要的理論意義和套用價值。
