蜂窩環(huán)上的全廣播算法

摘要：主要研究蜂窩環(huán)上的全廣播路由算法。第一個(gè)全廣播算法的設(shè)計(jì)思路是找到一條通過(guò)所有節(jié)點(diǎn)的路徑，關(guān)鍵是確定邊界上的一些特殊節(jié)點(diǎn)；第二個(gè)全廣播算法應(yīng)用了蜂窩環(huán)的哈密爾頓性質(zhì)。假設(shè)一個(gè)有n個(gè)處理機(jī)的蜂窩環(huán)，前者每個(gè)節(jié)點(diǎn)有自己專(zhuān)用的路由策略，時(shí)間復(fù)雜度為3n，因?yàn)橛?jì)算時(shí)間往往比數(shù)據(jù)傳送時(shí)間低得多，所以總的通信時(shí)間可以降低到n；后者是基于哈密爾頓圈的，需要n時(shí)間復(fù)雜度。到目前為止，這是第一次給出蜂窩環(huán)上全廣播算法。