传感技术学报
傳感技術學報
전감기술학보
Journal of Transduction Technology
2006年
3期
908-912,916
,共6页
边不交道路%二终端可靠性%无线传感器网络
邊不交道路%二終耑可靠性%無線傳感器網絡
변불교도로%이종단가고성%무선전감기망락
研究的问题是无线传感器网络中一些节点由于能量耗尽导致节点损坏而影响二终端网络可靠性的优化问题,提出了无线传感器网络中,m个节点被损毁情况下使得边不交道路可靠性最大的优化问题.通过引入s-t子图边不交道路可靠性的概念,本文建立了一个优化模型,在该模型中,当C0满足C0≥C(C是设计的启发式算法得到的最可靠的s-t子网中所包含的节点数),而被损毁的节点数m≤|V|-C时,给出了寻找源点与终端节点之间最大的s-t子图可靠性的启发式算法,即最大边不交道路可靠性算法,并证明了这个算法的计算复杂性是多项式时间的.仿真结果说明在损坏的节点数小于给定条件时该算法有效地处理该优化问题.此外也用类似的方法简单地处理了优化模型中C0≤C'时的最大s-t子图可靠性,其中C'是最短s-t道路中所含的点数.
研究的問題是無線傳感器網絡中一些節點由于能量耗儘導緻節點損壞而影響二終耑網絡可靠性的優化問題,提齣瞭無線傳感器網絡中,m箇節點被損燬情況下使得邊不交道路可靠性最大的優化問題.通過引入s-t子圖邊不交道路可靠性的概唸,本文建立瞭一箇優化模型,在該模型中,噹C0滿足C0≥C(C是設計的啟髮式算法得到的最可靠的s-t子網中所包含的節點數),而被損燬的節點數m≤|V|-C時,給齣瞭尋找源點與終耑節點之間最大的s-t子圖可靠性的啟髮式算法,即最大邊不交道路可靠性算法,併證明瞭這箇算法的計算複雜性是多項式時間的.倣真結果說明在損壞的節點數小于給定條件時該算法有效地處理該優化問題.此外也用類似的方法簡單地處理瞭優化模型中C0≤C'時的最大s-t子圖可靠性,其中C'是最短s-t道路中所含的點數.
연구적문제시무선전감기망락중일사절점유우능량모진도치절점손배이영향이종단망락가고성적우화문제,제출료무선전감기망락중,m개절점피손훼정황하사득변불교도로가고성최대적우화문제.통과인입s-t자도변불교도로가고성적개념,본문건립료일개우화모형,재해모형중,당C0만족C0≥C(C시설계적계발식산법득도적최가고적s-t자망중소포함적절점수),이피손훼적절점수m≤|V|-C시,급출료심조원점여종단절점지간최대적s-t자도가고성적계발식산법,즉최대변불교도로가고성산법,병증명료저개산법적계산복잡성시다항식시간적.방진결과설명재손배적절점수소우급정조건시해산법유효지처리해우화문제.차외야용유사적방법간단지처리료우화모형중C0≤C'시적최대s-t자도가고성,기중C'시최단s-t도로중소함적점수.