Ett uppkopplat Dominating Set (CDS) som fungerar som en virtuell ryggrad är ett effektivt sätt att minska omkostnaderna för routing i ett trådlöst sensornätverk. Dessutom är en kConnected m-Dominating Set (kmCDS) nödvändigt för feltolerans och routing flexibilitet. Vissa approximationsalgoritmer har föreslagits för att konstruera en kmCDS. De flesta av dem tar dock endast hänsyn till vissa specialfall där k = 1, 2 eller k ≤ m, eller inte är lätta att genomföra, eller har hög meddelande komplexitet. I detta dokument föreslår vi en ny distribuerad algoritm LDA med låg meddelande komplexitet att konstruera en kmCDS för allmänna k och m vars storlek garanteras vara inom en liten konstant faktor för den optimala lösningen när den maximala nodgraden är en konstant. Vi föreslår också en centraliserad algoritm ICGA med ett konstant prestandaförhållande för att konstruera en kmCDS. Teoretisk analys samt simuleringsresultat visas för att utvärdera de föreslagna algoritmerna.
Wu och Li REF föreslog en distribuerad algoritm med låg meddelande komplexitet för att konstruera en kmCDS för generiska värden av k och m. Detta tillvägagångssätt kräver en hög grad av redundans för nätverket topologi.
Construction algorithms for k-connected m-dominating sets in wireless sensor networks
{'venue': "MobiHoc '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}