蜂窩環上的全廣播算法

摘要：主要研究蜂窩環上的全廣播路由算法。第一個全廣播算法的設計思路是找到一條通過所有節點的路徑，關鍵是確定邊界上的一些特殊節點；第二個全廣播算法應用了蜂窩環的哈密爾頓性質。假設一個有n個處理機的蜂窩環，前者每個節點有自己專用的路由策略，時間復雜度為3n，因為計算時間往往比數據傳送時間低得多，所以總的通信時間可以降低到n；后者是基于哈密爾頓圈的，需要n時間復雜度。到目前為止，這是第一次給出蜂窩環上全廣播算法。