| 主权项 |
一种面向片上网络的永久故障容错路由控制方法，其特征在于：路由控制方法包括以下步骤： 1)确定一次通信的数据发送量，然后利用邻居置换元素优先级规则进行第一跳洪泛路由选择，具体过程如下： 首先，给出节点元素位置定义，节点的内部元素位置就是元素在节点中的排列位置，外部元素分为两种，当外部元素存在于目的节点中，其位置定义为0，如果外部元素不存在于目的节点中，则定义为‑1； 然后，根据排列环生成规则得到排列环组合，第一步是对内环进行优先级计算，根据首节点首元素是否相同确定最高优先级，然后根据内环排列依次优先级减1；接着是外环，利用到外环元素优先级规则，如果a的外部元素存在于目标节点b中，根据这些外部元素在b排列中的位置划分优先级，从b排列最后一个元素开始，如果首次碰到一个外部元素，则记录该外部元素在优先级表中，并给这个外部元素映射优先权值为内环元素最低优先级元素值减1，直到b的第一个元素结束，其中碰到外部元素，则添加到优先级表中，同时较上一个外部元素的权值减1； 2)第一条之后的路由选择利用(n,k)‑star graph节点排列环外部元素优先级规则选择确定性路由，(n,k)‑star graph是指(n,k)‑star graph拓扑结构；其中S<sub>n,k</sub>就是指(n,k)‑star graph，是一个无向图，顶点由<n>中取k个数的全排列构成，n和k为两个整数，且1≤k<n；a、b分别表示两个不同的节点，在S<sub>n,k</sub>上，从a＝a<sub>0</sub>a<sub>1</sub>...a<sub>k‑1</sub>到b＝b<sub>0</sub>b<sub>1</sub>…b<sub>k‑1</sub>的随机路由通信过程如下： (2.1)首先，根据邻居置换元素优先级规则得到a<sub>0</sub>除外的a中与其邻居相关的元素的优先级表，并计算出通信可靠阈值K<sub>min</sub>，同时生成K<sub>min</sub>份数据拷贝； (2.2)根据信息标志位判断是否为首次转发，如果是则进入(2.3)，如果不是则进入(2.4)； (2.3)根据(2.1)的K<sub>min</sub>值，从优先级表中得到K<sub>min</sub>个邻居置换元素，即优先级从高到低依次选取，节点a分别向K<sub>min</sub>个置换元素通过与节点a元素置换所得的邻居节点信息拷贝发送； (2.4)根据信息中目的节点信息，生成排列环外部元素优先级表； 2.4.1)如果a<sub>0</sub>＝b<sub>i</sub>，i≠0，那么将a<sub>0</sub>到第i个位置元素置换；如果置换后节点为坏点，则将a<sub>0</sub>与任意一个不包含a<sub>0</sub>的内环的任意元素置换； 2.4.2)如果a<sub>0</sub>＝b<sub>0</sub>，那么将a<sub>0</sub>与任意一个不在其正确位置的符号交换； 2.4.3)如果某个外环的外部符号在第一个位置，a<sub>x</sub>≠b<sub>y</sub>，a<sub>x</sub>为a的内部元素，b<sub>y</sub>为b的内部元素，那么将其与外环中没有固定的优先级最高的外部元素置换，如果有坏点则跳过到次优级元素置换，如果没有外部元素则置换，则与内圈不在其正确位置元素交换，如不成功，则说明链路不通。 |
