北京邮电大学学报
北京郵電大學學報
북경유전대학학보
JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS
2011年
5期
15-18,24
,共5页
闫中江%沈中%常义林%张颖%代亮
閆中江%瀋中%常義林%張穎%代亮
염중강%침중%상의림%장영%대량
无线传感器网络%部署算法%贪婪算法%整数线性规划
無線傳感器網絡%部署算法%貪婪算法%整數線性規劃
무선전감기망락%부서산법%탐람산법%정수선성규화
传感器节点的部署包括连通网络和非连通网络2种情况.为了最小化网络部署开销,对非连通网络的传感器节点部署问题进行了研究,建立了整数线性规划模型,并证明该问题为NP-complete问题.为找到该问题的近似最优解,通过理论分析确定了传感器节点的候选部署区域,提出了一种启发式的传感器节点贪婪部署算法,迭代地将传感器节点部署到覆盖目标点数最多的候选部署区域,直到覆盖所有目标点.通过仿真实验将所提出的贪婪部署算法和现有的遗传算法以及问题模型的最优解进行了比较,验证了算法的有效性.
傳感器節點的部署包括連通網絡和非連通網絡2種情況.為瞭最小化網絡部署開銷,對非連通網絡的傳感器節點部署問題進行瞭研究,建立瞭整數線性規劃模型,併證明該問題為NP-complete問題.為找到該問題的近似最優解,通過理論分析確定瞭傳感器節點的候選部署區域,提齣瞭一種啟髮式的傳感器節點貪婪部署算法,迭代地將傳感器節點部署到覆蓋目標點數最多的候選部署區域,直到覆蓋所有目標點.通過倣真實驗將所提齣的貪婪部署算法和現有的遺傳算法以及問題模型的最優解進行瞭比較,驗證瞭算法的有效性.
전감기절점적부서포괄련통망락화비련통망락2충정황.위료최소화망락부서개소,대비련통망락적전감기절점부서문제진행료연구,건립료정수선성규화모형,병증명해문제위NP-complete문제.위조도해문제적근사최우해,통과이론분석학정료전감기절점적후선부서구역,제출료일충계발식적전감기절점탐람부서산법,질대지장전감기절점부서도복개목표점수최다적후선부서구역,직도복개소유목표점.통과방진실험장소제출적탐람부서산법화현유적유전산법이급문제모형적최우해진행료비교,험증료산법적유효성.
