软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2010年
10期
2656-2665
,共10页
无线传感器网络%网络生命期%节点调度%最小覆盖集%贪婪算法%近似算法
無線傳感器網絡%網絡生命期%節點調度%最小覆蓋集%貪婪算法%近似算法
무선전감기망락%망락생명기%절점조도%최소복개집%탐람산법%근사산법
网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.
網絡生命期是限製無線傳感器網絡髮展的一箇瓶頸.在保證網絡鑑控性能的前提下,僅調度部分節點工作而讓其餘節點處于低功耗的休眠狀態,可以有效節省能耗,延長網絡生命期.節點調度的目標是尋找一箇能夠覆蓋鑑控區域的最小節點集閤,這是一箇NP難問題,目前,其近似算法的性能較低.提齣瞭一種基于貪婪法的最小覆蓋集近似算法,在構造覆蓋集的過程中,優先選擇擴展麵積最大的有效節點加入覆蓋集.理論分析錶明,該算法能夠構造齣較好的覆蓋集,時間複雜度為O(n),其中,n為初始節點總數.實驗數據錶明,該算法的性能要優于現有算法,得到的覆蓋集的平均大小比現有算法減小瞭14.2%左右,且執行時間要短于現有算法.噹初始節點分佈較密時,該算法得到的平均覆蓋度小于1.75,近似比小于1.45.
망락생명기시한제무선전감기망락발전적일개병경.재보증망락감공성능적전제하,부조도부분절점공작이양기여절점처우저공모적휴면상태,가이유효절성능모,연장망락생명기.절점조도적목표시심조일개능구복개감공구역적최소절점집합,저시일개NP난문제,목전,기근사산법적성능교저.제출료일충기우탐람법적최소복개집근사산법,재구조복개집적과정중,우선선택확전면적최대적유효절점가입복개집.이론분석표명,해산법능구구조출교호적복개집,시간복잡도위O(n),기중,n위초시절점총수.실험수거표명,해산법적성능요우우현유산법,득도적복개집적평균대소비현유산법감소료14.2%좌우,차집행시간요단우현유산법.당초시절점분포교밀시,해산법득도적평균복개도소우1.75,근사비소우1.45.
