Abstract-Efficient routing bland en uppsättning mobila värdar är en av de viktigaste funktionerna i ad hoc trådlösa nätverk. Routing baserat på en ansluten dominerande uppsättning är ett lovande tillvägagångssätt, där sökområdet för en rutt reduceras till värdarna i uppsättningen. En uppsättning dominerar om alla värdar i systemet är antingen i uppsättningen eller grannar av värdar i uppsättningen. Effektiviteten hos dominerande uppsättningsbaserad routing beror främst på de omkostnader som införs i bildandet av den dominerande uppsättningen och storleken på den dominerande uppsättningen. I detta dokument går vi först igenom en lokal formation av en ansluten dominerande uppsättning som kallas märkningsprocess och dominerande-uppsättning-baserad routing. Sedan föreslår vi en dominant beskärningsregel för att minska storleken på den dominerande uppsättningen. Denna dominerande beskärningsregel (s.k. regel k) är en generalisering av två befintliga regler (s.k. regel 1 respektive regel 2). Vi bevisar att den vertex uppsättning som härleds genom att tillämpa regel k fortfarande är en ansluten dominerande uppsättning. Regel k är mer effektiv när det gäller att minska den dominerande uppsättningen som härrör från märkningsprocessen än kombinationen av artiklarna 1 och 2 och, överraskande, i ett begränsat genomförande med lokal information, regel k har samma kommunikations komplexitet och mindre beräkning komplexitet. Simuleringsresultat bekräftar att regel k överträffar reglerna 1 och 2, särskilt i nätverk med relativt hög vertexgrad och hög andel enkelriktade länkar. Vi bevisar också att det finns en övre gräns på den genomsnittliga storleken på den dominerande uppsättningen som härleds från regel k i dess begränsade genomförande.
I REF tillhandahåller författarna en märkningsprocess tillsammans med två dominerande beskärningsregler för att minska storleken på en dominerande uppsättning.
An extended localized algorithm for connected dominating set formation in ad hoc wireless networks
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': 'IEEE Transactions on Parallel and Distributed Systems', 'mag_field_of_study': ['Computer Science']}