無線感測器網路中的若干計算幾何問題研究

《無線感測器網路中的若干計算幾何問題研究》是依託山東大學，由呂琳擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：無線感測器網路中的若干計算幾何問題研究
• 項目類別：青年科學基金項目
• 項目負責人：呂琳
• 依託單位：山東大學

中文摘要

無線感測器網路是當今國內外備受關注的、由多學科高度交叉的新興前沿研究領域。感測器的部署及覆蓋是其中的一個關鍵問題，即通過一定的算法放置或移動節點，最佳化節點分布，合理分配網路的空間資源，以期網路在套用中利用率最大化或單個任務能量消耗最小化，從而更好的完成環境感知、信息獲取等任務，並提高網路生存能力。.本項目主要研究無線感測器網路部署及最優覆蓋中的幾何問題，具體包括：已知多邊形區域中的無線感測器最優覆蓋問題、未知多邊形區域中的無線感測器動態部署問題和無線感測器的多重覆蓋問題。針對不同的套用環境對這些問題建立形式化描述，分析其幾何特性，分別基於幾類廣義Voronoi圖建立其幾何最佳化模型，然後利用計算幾何算法進行最佳化求解，並基於上述理論成果研發系統原型，為無線感測器網路的研究與套用提供有力的幾何工具，豐富計算幾何特別是Voronoi圖的套用研究領域和內容。

結題摘要

無線感測器網路（WSN）是當今國內外備受關注的、由多學科高度交叉的新興前沿研究領域。感測器的部署及覆蓋是其中的一個關鍵問題，即通過一定的算法放置或移動節點，最佳化節點分布，合理分配網路的空間資源，以期網路在套用中利用率最大化或單個任務能量消耗最小化，從而更好的完成環境感知、信息獲取等任務，並提高網路生存能力。 在本項目的資助下，我們首先研究了WSN在已知區域的最佳化覆蓋問題，基於已有的基於均勻區域的覆蓋算法，提出了非均勻區域內的最佳化覆蓋算法，研發了WSN互動部署仿真平台軟體。對於未知區域的動態部署問題，我們重點研究了其中可見性計算的加速算法，包括多邊形中點的可見性計算與NURBS曲線路徑的弱可見區域計算。進一步的，我們研究了重心Voronoi圖的擴展與套用，提出了包括基於流線重心 Voronoi 圖的流場布局算法，基於能量圖的圓排列最佳化算法，並套用於圖像拼貼與層次數據可視化布局等問題中，基於擴展 Voronoi 圖的泊松分布最佳化算法。另外，面向3D 列印這一近年來蓬勃發展的領域，我們基於 Voronoi 圖的相關理論，針對其中三維物體的結構最佳化與形狀處理等問題進行了一系列的探索。所取得的成果為無線感測器網路中覆蓋與部署問題的研究與套用提供了有力的幾何工具，豐富了計算幾何特別是 Voronoi 圖的套用研究領域和內容。 在項目執行期內，在圖形學頂級期刊ACM Transactions on Graphics (TOG)上發表論文2篇，其它SCI期刊論文2篇，EI論文5篇，出版學術專著1部，申請專利9項，已授權3項，軟體著作權1項，培養碩士生 4 名、博士生 1 名。