无线传感器网络最小连通覆盖集问题求解算法

《无线传感器网络最小连通覆盖集问题求解算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据ISSN1000·9825．CODENRUXUEWJournalofSoftware，Vol17，No2，February2006，PP175—184DOI：1013604{osl70175@2006byJournalofSoftwareAllrightsreserved无线传感器网络最小连通覆盖集问题求解算法蒋杰1+，方力2，张鹤颖1，窦文华1(国防科学技术大学计算机学院，湖南长沙410073)2(国防科学技术大学网络信息中心，湖南长沙410073)E—mail：jOS@iscasa0

2、cnhnp：／／www,iosOrgcnh坤㈣+8610—62562563AnAlgorithmforMinimalConnectedCoverSetProbleminWirelessSensorNetworksJIANGJie”，FANGLi2，ZHANGHe．Yin91，DOUWen-Hua。(SchoolofCoraputer，NationalUniversityofDefenseTechnology，Changsha410073，China)2(NetworkInformationCen

3、ter，NationalUniversityofDefenseTechnology，Cllmlgsha410073，China)+Correspondingauthor：Phn：+86-731—4575830，Fax：+86—731·4575830，E-mail：jian鲥ie@nudteducn，hnp：／／wlvwnudteducnJiangJ，FangL，ZhangHY，DouWⅡ．Analgorithmforminimalconnectedcoversetprobleminwireles

4、ssensornetworks．JournalofSoftware，2006，17(2)：175—184．http：／／www．josorgcn／1000—9825／17／175．htmAbstract：ReducingpowerconsumptiontoextendnetworklifetimeisoneofthemostimportantchallengesindesigningwirelesssensornetworksOnepromisingapproachtoconservingsys

5、temenergyistokeeponlyaminimalnumberofsensorsactiveandputothersintolow-poweredsleepmode，whiletheactivesensorscarlmaintainthecommunicationconnectivityandcoverthetargetregioncompletelyTheproblemofcomputingsuchminimalactivesensorsetisNP·hard．Inthispaper，

6、acentralizedVomnoitessellation(CVT)basedapproximatealgorithmisproposedtoconstructanearoptimalcoversetofactivesensorsrequiredtocoverthetargetregioncompletelyThecommunicationgraDhinducedbythecoversetcomputedbyCVTalgorithmisconnectedifsensor’scommunicat

7、ionradiusisatleasttwiceofitssensingradius．Incaseofsensor’scommunicationradiusissmallerthantwiceofitssensingradius，aminimumspanningtree(MST)basedconnectionalgorithmisproposedtoensarethecommunicationconnectivityofthecoverset．Finally，theperformanceofthe

8、proposedalgorithmisevaluatedthroughtheoreticalanalysisandextensivenumericalexperiments．ExperimentalresultsshowthattheproposedalgorithmoutperformsthegreedyalgorithmintermsofthemntimeandthesizeoftheconstructedconnectedcoversetKeywords：WSN(wirelesssenso