Denna forskning motiveras av en del distribuerade schemaläggningsproblem i distribuerade sensornätverk, där beräknings- och kommunikationsresurser är knappa. Vi kastar först dessa problem som distribuerade begränsningar tillfredsställelse problem (DisCSPs) och distribuerade begränsningar optimering problem (DisCOPs) och modellera dem som distribuerade graf färgning. För att klara av begränsade resurser och begränsat realtidskrav är det absolut nödvändigt att använda distribuerade algoritmer som har låga omkostnader på resursförbrukning och hög kvalitet när som helst prestanda. För att uppfylla dessa krav studerar vi två befintliga DisCSP-algoritmer, distribuerad stokastisk sökalgoritm (DSA) och distribuerad breakoutalgoritm (DBA), för att lösa disCOPs och de distribuerade schemaläggningsproblemen. Vi visar experimentellt att DSA har en fas-övergång eller tröskel beteende, genom att dess lösning kvalitet degenererar abrupt och dramatiskt när graden av parallella avrättningar av distribuerade agenter ökar bortom något kritiskt värde. Vi överväger också fullständigheten och komplexiteten i DBA för distribuerad graf färgning. Vi visar att DBA är komplett på färga acykliska grafer, färga en acyklisk graf av n noder i O(n 2 ) steg. På ett cykliskt diagram kan dock DBA aldrig avslutas. Till 56 W. Zhang et al. / Artificiell intelligens 161 (2005) förbättra DBA: s prestanda på färgning cykliska grafer, föreslår vi två stokastiska variationer. Slutligen jämför vi DSA och DBA direkt för att lösa distribuerade graffärger och distribuerade schemaläggningsproblem i sensornätverk. Resultaten visar att DSA är överlägsen DBA när det kontrolleras korrekt, har bättre eller konkurrenskraftig lösningskvalitet och betydligt lägre kommunikationskostnader än DBA. DSA är därför valets algoritm för våra distribuerade schemaläggningsproblem och andra distribuerade problem med liknande egenskaper.
Distributed Breakout Algorithm (DBA) och Distribuated Stochastic Algorithm (DSA) REF är de två mest populära ofullständiga metoderna för att lösa DCOP.
Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks
{'venue': 'Artif. Intell.', 'journal': 'Artif. Intell.', 'mag_field_of_study': ['Computer Science']}