[發(fā)明專利]一種LKH密鑰管理樹動(dòng)態(tài)平衡方法

有效

• 申請?zhí)枺?/td>: 201310176324.6
• 申請日: 2013-05-14
• 公開（公告）號: CN103281175A
• 公開（公告）日: 2013-09-04
• 發(fā)明（設(shè)計(jì)）人: 徐杰;尹華云;孫健;隆克平
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: H04L9/08
• 分類號: H04L9/08
• 代理公司: 成都行之專利代理事務(wù)所(普通合伙) 51220
• 代理人: 溫利平

1.一種LKH密鑰管理樹動(dòng)態(tài)平衡方法，其特征在于，包括以下步驟：

（1）、定義變量N_J和N_D分別表示加入和離開密鑰管理組的用戶數(shù)目；

（2）、對加入和離開密鑰管理組的用戶數(shù)目N_J和N_D進(jìn)行判斷；

2.1）、當(dāng)加入用戶數(shù)量N_J>離開用戶數(shù)量N_D，則執(zhí)行：

a1、選擇數(shù)量為N_D的加入用戶替代原始密鑰管理樹中的離開用戶；

a2、將剩余的加入用戶和原始密鑰管理樹合并為一棵新的密鑰管理樹：將加入用戶看成單個(gè)節(jié)點(diǎn)的密鑰管理樹，將單節(jié)點(diǎn)密鑰管理樹和原始密鑰管理樹組成一個(gè)待合并密鑰管理樹集合，從待合并密鑰管理樹集合選擇兩棵高度最小的密鑰管理樹，將其合并為一棵密鑰管理樹并置于待合并密鑰管理樹集合，同時(shí)從待合并密鑰管理樹集合中刪除這兩個(gè)高度最小的密鑰管理樹；在待合并密鑰管理樹集合中再選擇兩棵高度最小的密鑰管理樹進(jìn)行合并，這樣重復(fù)，直至只剩下一棵密鑰管理樹為止，該密鑰管理樹為新的密鑰管理樹；

2.2）、當(dāng)加入用戶數(shù)量N_J=用戶數(shù)量離開用戶數(shù)量N_D，只需用加入用戶替代原始密鑰管理樹中離開用戶，得到新的密鑰管理樹即可；

2.3）、當(dāng)加入用戶數(shù)量N_J<離開用戶數(shù)量N_D，執(zhí)行：

b1、用所有加入用戶替代原始密鑰管理樹中的數(shù)目為N_J的離開用戶；

b2、在原始密鑰管理樹中刪除未被替代的離開用戶，并進(jìn)行節(jié)點(diǎn)刪除：

若原始密鑰管理樹中節(jié)點(diǎn)缺少右節(jié)點(diǎn)子樹或左節(jié)點(diǎn)子樹，此節(jié)點(diǎn)將會(huì)被它剩下的節(jié)點(diǎn)子樹替代；

b3、從下到上，從右至左依次檢查原始密鑰管理樹中的每個(gè)節(jié)點(diǎn)是否為平衡節(jié)點(diǎn)，若節(jié)點(diǎn)不平衡，則合并不平衡節(jié)點(diǎn)的左右子樹，并用新合并形成的子樹替代不平衡節(jié)點(diǎn)，得到新的密鑰管理樹；

（3）、密鑰管理中心根據(jù)新的密鑰管理樹即平衡密鑰管理樹中節(jié)點(diǎn)變化情況產(chǎn)生密鑰更新消息和位置更新消息，對組密鑰進(jìn)行管理。

2.根據(jù)權(quán)利要求1所述的LKH密鑰管理樹動(dòng)態(tài)平衡方法，其特征在于，步驟2.1）、步驟2.3）中所述的合并為：

待合并的兩棵密鑰管理樹為Tree1和Tree2，并且密鑰管理樹Tree1和Tree2的最大高度為H_{Max_Tree1}≥H_{Max_Tree2}；

c1、當(dāng)密鑰管理樹Tree1的最大高度H_{Max_Tree1}-密鑰管理樹Tree2的最小高度H_{Min_Tree2}≤1時(shí)，采用合并方法一進(jìn)行合并即：創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將密鑰管理樹Tree1和Tree2作為新建節(jié)點(diǎn)的左右子樹，新建節(jié)點(diǎn)即為合并后的平衡密鑰管理樹的根節(jié)點(diǎn)；

c2、當(dāng)密鑰管理樹Tree1的最大高度H_{Max_Tree1}-密鑰管理樹Tree2的最小高度H_{Min_Tree2}>1，且密鑰管理樹Tree1的最大高度最小高度相等即H_{Max_Tree1}=H_{Min_Tree1}時(shí)，采用合并方法二進(jìn)行合并，即：

第一步、計(jì)算出密鑰管理樹Tree1和Tree2最大高度H_{Max_Tree1}、H_{Max_Tree2}的差值h即h=H_{Max_Tree1}-H_{Max_Tree2}；

第二步、在密鑰管理樹Tree1第h層上，從左至右尋找一個(gè)待更新節(jié)點(diǎn)，若存在這樣的節(jié)點(diǎn)，標(biāo)記它；若不存在這樣的節(jié)點(diǎn)，標(biāo)記密鑰管理樹Tree1第h層上最后一個(gè)節(jié)點(diǎn)；

第三步、創(chuàng)建一個(gè)新的節(jié)點(diǎn)替代第二步標(biāo)記的節(jié)點(diǎn)，并將密鑰管理樹Tree2和以標(biāo)記節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹作為新建節(jié)點(diǎn)的左右子樹；

c3、當(dāng)密鑰管理樹Tree1的最大高度H_{Max_Tree1}-密鑰管理樹Tree2的最小高度H_{Min_Tree2}>1，且密鑰管理樹Tree1的最大高度最小高度不相等即H_{Max_Tree1}≠H_{Min_Tree1}時(shí)，采樣合并方法三進(jìn)行合并：

第一步、定義參數(shù)：

Set_M表示一個(gè)容器，用來儲存密鑰管理樹Tree1的最小高度子樹；

Set_T表示一個(gè)容器，用來儲存待合并的密鑰管理樹，最初容器中只包含密鑰管理樹Tree2；

Num_M表示容器Set_M中最小高度子樹的數(shù)目；

H_i表示容器Set_M中第i棵最小高度子樹的最大高度；

MinTree_H_i表示高度為H_i的最小高度子樹；

H_MergeTree表示容器Set_T中高度最大的樹；

第二步：找出密鑰管理樹Tree1所有的最小高度子樹，并按最大高度由大到小將這些最小高度子樹記錄在容器Set_M中，即有H₁≥…≥H_{Num_M}；

第三步：在容器Set_T中找出最大高度為最大的密鑰管理樹H_MergeTree；

第四步：比較密鑰管理樹H_MergeTree和容器Set_M中最小高度子樹的最大高度，存在以后三種情形：

情形1：當(dāng)密鑰管理樹H_MergeTree的最大高度H_{Max_H_MergeTree}等于最小高度子樹MinTree_H_i的最大高度H_i（1≤i≤Num_M）即H_{Max_H_MergeTree}=H_i，則采用合并方法一的方法對密鑰管理樹H_MergeTree、最小高度子樹MinTree_H_i進(jìn)行合并；其次用合并得到密鑰管理樹替代密鑰管理樹Tree1中的MinTree_H_i，最后將H_MergeTree從容器Set_T刪除；

情形2：當(dāng)密鑰管理樹H_MergeTree的最大高度H_{Max_H_MergeTree}小于最小高度子樹MinTree_H_i的最大高度H_i且大于最小高度子樹MinTree_H_i+1的最大高度H_i+1即H_{Max_H_MergeTree}<H_i且H_{Max_H_MergeTree}>H_i+1（i≠Num_M）時(shí)，如果H_i-H_{Min_H_MergeTree}>1，用合并方法二的方法合并密鑰管理樹H_MergeTree和最小高度子樹MinTree_H_i；否則利用合并方法一的方法合并H_MergeTree和MinTree_H_i，并用新合并的密鑰管理樹替代密鑰管理樹Tree1中的MinTree_H_i，最后將H_MergeTree從容器Set_T刪除；

情形3：當(dāng)密鑰管理樹H_MergeTree的最大高度H_{Max_H_MergeTree}小于最小高度子樹MinTree_H₁的最大高度H₁時(shí)，密鑰管理樹H_MergeTree不可能一次性合并至密鑰管理樹Tree1中，采取將密鑰管理樹H_MergeTree分解的措施，分步將其合并至密鑰管理樹Tree1：

c31、在密鑰管理樹H_MergeTree中搜索一棵高度為H₁的子樹，記為子樹H_MergeTree_H₁；

c32、標(biāo)記子樹H_MergeTree_H₁的父節(jié)點(diǎn)到密鑰管理樹H_MergeTree根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)，移去標(biāo)記節(jié)點(diǎn)后，將除子樹H_MergeTree_H₁外的其他剩余子樹添加記錄到容器Set_T；

c33、利用合并方法一的方法合并子樹H_MergeTree_H₁和最小高度子樹MinTree_H₁，并用合并后的子樹替代密鑰管理樹Tree1中的最小高度子樹MinTree_H₁；

c34、從容器Set_T中刪除密鑰管理樹H_MergeTree；

第五步：檢查容器Set_T是否為空，若為空則合并完成，否則清空容器Set_M，返回第一步；

其中，所述合并步驟中，所述的密鑰管理樹的最大高度其在數(shù)值上等于密鑰管理樹根節(jié)點(diǎn)的最大高度即根節(jié)點(diǎn)到其孩子節(jié)點(diǎn)的最大長度路徑，密鑰管理樹的最小高度其在數(shù)值上等于密鑰管理樹根節(jié)點(diǎn)的最小高度即跟節(jié)點(diǎn)到其孩子節(jié)點(diǎn)的最小路徑長度；

所述的平衡節(jié)點(diǎn)為如果節(jié)點(diǎn)的最大高度和最小高度之差不超過1，則稱此節(jié)點(diǎn)為平衡節(jié)點(diǎn)；

所述的平衡密鑰管理樹為若密鑰管理樹中所有節(jié)點(diǎn)都為平衡節(jié)點(diǎn)，則稱此密鑰管理樹為平衡密鑰管理樹；

所述的樹的層為設(shè)定密鑰管理樹的根節(jié)點(diǎn)位于第1層，層數(shù)從根節(jié)點(diǎn)層次開始依次加1；

所述的最小高度子樹為在一棵非完全的平衡密鑰管理樹中，若節(jié)點(diǎn)的最小高度和最大高度相等但其父節(jié)點(diǎn)的最小高度和最大高度不相等，定義由此節(jié)點(diǎn)及其所有孩子節(jié)點(diǎn)組成的子樹為最小高度子樹。