[發(fā)明專(zhuān)利]一種針對(duì)片上網(wǎng)絡(luò)的低復(fù)雜度和可擴(kuò)展的容錯(cuò)路由算法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010167572.0
• 申請(qǐng)日: 2010-05-06
• 公開(kāi)（公告）號(hào): CN101834797A
• 公開(kāi)（公告）日: 2010-09-15
• 發(fā)明（設(shè)計(jì)）人: 石澤文;虞志益;曾曉洋;陳秀平;惠志達(dá);楊金達(dá)
• 申請(qǐng)（專(zhuān)利權(quán)）人: 復(fù)旦大學(xué)
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56;H04L1/00
• 代理公司: 上海正旦專(zhuān)利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種針對(duì)片上網(wǎng)絡(luò)的低復(fù)雜度和可擴(kuò)展的容錯(cuò)路由算法，其特征在將系統(tǒng)分為如下不同區(qū)域：一個(gè)中心區(qū)域、四個(gè)邊界區(qū)域和四個(gè)角部，區(qū)域；每個(gè)區(qū)域采用各自的容錯(cuò)路由策略，各個(gè)區(qū)域單獨(dú)可以容納位于該區(qū)域的各種出錯(cuò)形式，同時(shí)它們又可以很好的協(xié)同工作以容納那些跨越若干區(qū)域的出錯(cuò)情況；在路由器的東、南、西、北四個(gè)輸出端口分別定義若干個(gè)比特位，包括2個(gè)路由限制位和一個(gè)連接位，其中路由限制位表征從某個(gè)端口輸出時(shí)能否在下一跳進(jìn)行某個(gè)方向的跳轉(zhuǎn)；連接位則表征從某一端口看出去跟周?chē)墓?jié)點(diǎn)是否連接，‘1’則連接，‘0’則斷開(kāi)，具體容錯(cuò)路由算法的步驟如下：

1)根據(jù)當(dāng)前節(jié)點(diǎn)位置和目標(biāo)節(jié)點(diǎn)位置的相對(duì)信息，給出初步的東、南、西、北四個(gè)方位信息E1，N1，W1，S1；

2)根據(jù)路由限制位信息和第一步求解的大致方位信息，給出候選的路由輸出端口信息N2，S2，E2，W2，計(jì)算如公式(1)所示：

N2=N1·E1‾·W1‾+N1·E1·Rne+N1·W1·Rnw]]>

E2=E1·N1‾·S1‾+E1·N1·Ren+E1·S1·Res]]>

S2=S1·E1‾·W1‾+S1·E1·Rse+S1·W1·Rsw---(1)]]>

W2=W1·N1‾·S1‾+W1·N1·Rwn+W1·S1·Rws]]>

3)根據(jù)第二步給出的候選端口和連接位信息，通過(guò)仲裁給出最終的輸出端口南，北，東，西N，S，E和W，計(jì)算如公式(2)所示：

N＝N2·C_n

E＝E2·C_e

?????????????(2)；

S＝S2·C_s

W＝W2·C_w

其中，限制位Rns表示從當(dāng)前節(jié)點(diǎn)的北端口輸出后下一步能否向南部轉(zhuǎn)彎，其他限制位的解釋類(lèi)似；連接位CCn，Ce，Cs和Cw則分別代表著各個(gè)方向的連接位信息，如果連接則配置為‘1’，否則配置為‘0’。