《無線網路中一些圖論與組合最佳化問題》是依託鄭州大學，由尚衛苹擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：無線網路中一些圖論與組合最佳化問題
- 項目類別：青年科學基金項目
- 項目負責人：尚衛苹
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
無線感測器網路作為一個新興的套用領域，必然會帶來許多新的研究問題，其中主要包括拓撲控制、數據融合、路由協定、覆蓋問題等等。由於感測器節點通常攜帶能量有限的電池，網路中最佳化問題的首要設計目標是能源的高效使用。本項目著重探討兩類基本問題：（1）能量高效與最短時間的數據融合，（2）最小能量或最小干擾的拓撲控制。我們擬對無線網路的數據融合、最小能量（連通）控制集以及最小干擾數等方面提出的一系列新型的網路最佳化問題進行算法研究，特別設計這些問題的具有良好性能保證的近似算法。
結題摘要
感測器網路作為一個新興的套用領域，帶來許多新的研究問題，其中主要包括拓撲控制，數據融合，路由協定，覆蓋問題等。我們主要研究了網路中能量高效與最短時間的數據融合問題、最小控制集問題的計算複雜性和近似算法； 圖論中二維頻寬問題、匹配可擴問題；工件排序問題等。受本項目資助共發表學術論文12篇；還有3篇接收待發表。其中代表性成果如下：（1）對於最短時間的數據融合問題設計了具有常數近似比的算法；（2）對單位圓盤圖中Roman控制集問題給出了NP-困難性證明和近似算法；（3）對具有容量限制的最小控制集與連通控制集問題給出了這兩個問題近似比分別為6和9的近似算法；（4）對於二維頻寬問題研究了基本性質，上下界以及精確結果。
