[發明專利]一種物聯網中設備節點的匿名化方法

有效

• 申請號: 202011068146.1
• 申請日: 2020-10-08
• 公開（公告）號: CN112202790B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 牛少勇
• 申請（專利權）人: 杭州肥牛信息科技有限公司
• 主分類號: H04L9/40
• 分類號: H04L9/40;H04L41/00
• 代理公司: 杭州廣奧專利代理事務所(特殊普通合伙) 33334
• 代理人: 尹建民

1.一種物聯網中設備節點的匿名化方法，包括定義過程和匿名化過程，其特征在于：

所述定義過程包括：

定義1：設定一個無向圖是一個有序的二元組(V,E)，記作G(V,E)，其中，

V≠φ稱為G的節點集，其元素稱為圖的節點；

E稱為G的邊集，其元素稱為無向邊，簡稱圖的邊；

既不含平行邊又不含圈的無向圖，簡稱簡單無向圖；

定義2：設一個簡單無向圖G＝(V,E)，其中n＝|V|≥1，若圖G中每個節點均與其余的n-1個節點相連接，則稱G為n階無向完全圖，若圖G中E＝φ，則稱G為零圖；

定義3：設一個簡單無向圖G＝(V,E)，對于任意的v∈V，v作為圖G中邊的端點的次數之和，稱為v的度數，簡稱度，記作d_G(v)，為避免混淆，用d_G代表圖G中所有節點的度序列，即d_G是一個含有n＝|V|個元素的序列，用d(i)、d(v_i)、d_i均可代表圖G中第i個節點(v_i∈V)的度數；

定義4：設一個簡單無向圖G＝(V,E)，其中n＝|V|，不是一般性，假設圖中所有節點的度數按遞減順序排列，即，d(1)≥d(2)≥…≥d(n)，對于ij，稱d[i,j]為d_G中i,i+1,……,j,j+1等元素組成的子序列；

定義5：設一個簡單無向圖G＝(V,E)，對于任意兩個節點v_i,v_j∈V，若存在邊e_k∈E，使得e_k＝(v_i,v_j)，則稱v_i與v_j是彼此相鄰的，簡稱是相鄰的，對任意v∈V，稱{u|u∈V,(u,v)∈E,且u≠v}為v的鄰域；

定義6：給定一個序列V，如果對于序列V中的任何一個元素，在這個序列中與此元素相等的其它元素至少出現k-1次，那么，就稱此序列為k-匿名序列；

定義7：給定一個簡單無向圖G＝(V,E)，如果圖G的節點度數構成的遞減序列d_G是k-匿名序列，即，對于圖中任何一個節點v∈V，在圖中至少存在其它k-1個點與此節點具有相同的度數，那么，就稱此圖G為k-度匿名圖；

推論1：如果一個簡單無向圖G＝(V,E)是k₁-度匿名圖，且k₂≤k₁，那么此圖也是k₂-度匿名圖；

推論2：如果一個簡單無向圖G＝(V,E)是k-度匿名圖，僅知道其中某一個節點v∈V的度數，則要從圖中唯一判斷出該節點的概率為p(v)≤1/k；

定義8：設一個簡單無向圖G＝(V,E)是k-度匿名圖，在不改變原圖G的基礎上，增加一些節點以及這些節點和原圖中一些節點的關系，組成的圖設為之后在圖中添加最少的邊，使圖也達到k-度匿名，將這種匿名化過程稱為動態圖匿名化；

定義9：給定一個非負整數序列d_G，并且d(1)≥d(2)≥…≥d(n)，如果存在一個簡單無向圖G，節點度數序列恰好是d_G，那么就稱序列d_G是可簡單圖化的；

定義10：設一個簡單無向圖G＝(V,E)，假設n個節點按照某種任意方式編號1,2,…,n,其中n＝|V|，則圖G＝(V,E)的鄰接矩陣是一個|V|×|V|的矩陣A＝(a_ij)，滿足：

設A＝(a_ij)的特征值和特征向量分別為λ_i,e_i，其中,

λ₁≥λ₂≥,…,≥λ_n，e_i＝(x₁,x₂,…,x_n)^T；

定義11：設λ_i(i＝1,2,…,n)是矩陣A的特征向量，e_i是相應的特征向量，其中，λ₁≥λ₂≥,…,≥λ_n，e_i＝(x₁,x₂,…,x_n)^T，則矩陣A的譜分解為：

定義12：給定一個無向，無權重圖G＝(V,E)，設d(v₁,v₂)是v₁和v₂之間的最短路徑長度，當v₁＝v₂或者從v₁無法到達v₂或者從v₂無法到達v₁時，令d(v₁,v₂)＝0，定義此圖的平均路徑長度l_G為：

其中，n＝|V|，v₁,v₂∈V；

定義13：給定一個無向圖G＝(V,E)，對于節點v∈V，定義節點v的聚集系數為：

其中，k表示節點v的所有鄰居之間的邊數，d(v)表示節點v的度數；

定理1(握手定理)：設一個簡單無向圖G＝(V,E)，V＝{v₁,v₂,…,v_n}，m＝|E|，則有

定理2(可簡單圖化定理)：設非負整數序列d＝(d₁,d₂,…,d_n), 且有(n-1)≥d₁≥d₂≥,…,≥d_n≥0，則d可簡單圖化，當且僅當是可簡單圖化的；

定理3：設A為圖G＝(V,E)的鄰接矩陣，G＝(V,E)經轉換邊擾動處理之后的圖為是的鄰接矩陣，λ₁≥λ₂≥,…,≥λ_n，e_i＝(x₁,x₂,…,x_n)^T為A的特征值和特征向量，如果在圖G＝(V,E)中任選兩條邊(t,w)和(u,v)，之后把這兩條邊轉換成(t,v)和(u,w)，則有如下結論成立，

(1)如果(x_t-x_u)(x_v-x_w)0，那么的最大特征值滿足：其中x_t是λ₁對應的特征向量e₁＝(x₁,x₂,…,x_n)^T的第t個分量；

(2)如果(x_t-x_u)(x_v-x_w)0和那么的最大特征值滿足：其中x_t是λ₁對應的特征向量e₁＝(x₁,x₂,…,x_n)^T的第t個分量；

所述匿名化過程包括：

1)圖的抽象化：將物聯網絡圖抽象為圖論中的簡單無向圖，將網絡中的設備節點視為圖的節點，將網絡中設備節點之間的連接關系視為圖的邊；

2)初始化圖模型：創建一個簡單無向圖，把節點和邊加入到圖中；

3)把物聯網絡圖的節點度數序列做成k-匿名序列，簡稱度數序列匿名化；

4)根據k-匿名序列構造出k-度匿名物聯網絡圖；

5)對匿名化后的圖進行轉換邊的擾動算法處理；

6)記錄上述過程中新添加/刪除的邊；

其中，

所述匿名化過程的步驟3的偽代碼實現過程為：

輸入：一個單調遞減序列d_G和一個非負整數k；

輸出：返回一個正整數值sum，此值表示在序列d_G做成k-匿名化序列的過程中添加度數總和的最小值；

1：n←d_G中元素的個數；

2：新建一個數組sum[n]，其中數組的長度為n，新建一個空鏈表list；

3：for i←n,…,1；

4：如果i2k，則計算出

5：如果i≥2k，則令start←max(k,i-2k+1)；

6：for t←i-k,…,start；

7：for j←i,…,t+1；

8：計算

9：把tempSum放入一個鏈表list中；

10：取出鏈表list中的最小值，并放入sum[i]中；

11：重復第2步到第9步；

12：停止并返回數組中的最后一個元素,記為sum；

此算法的時間復雜度為O(nk)，通過此算法即得到一個k-匿名化序列

所述匿名化過程的步驟4的偽代碼實現過程為：

輸入：含有n個元素的k-匿名化序列

輸出：如果序列可簡單圖化，則輸出一個以序列為節點度數的簡單無向k-度匿名圖否則，輸出“序列不可簡單圖化”；

1：

2：如果的值是奇數，則

3：停止并返回“序列不可簡單圖化”；

4：while(1)do；

5：如果序列中存在d(i)0,則

6：停止并返回“序列不可簡單圖化”；

7：如果序列中的元素全部為0，則

8：停止并返回圖

9：否則，取當前序列中度數最大的節點假設度數為

10：記是中除了節點之外的，度數是前大的節點組成的集合；

11：令

12：fordo；

13：

14：

15：停止并返回圖

此算法的時間復雜度為O(nd_max)；

所述匿名化過程的步驟5的偽代碼實現過程為：

輸入：圖G＝(V,E)和一個參數ε∈[0,1]，其中n₁＝|E|；

輸出：擾動之后的圖

1：計算出圖G的鄰接矩陣A；

2：分別計算出鄰接矩陣A的特征值和特征向量(λ₁,λ₂,e₁)；

3：令m＝[n₁ε]，即對n₁ε取整；

4：令t＝0；

5：while(t＝m)do；

6：如果t是偶數；

7：在圖G中任意取一條邊(t,w)；

8：依據定理3在圖G中尋找所有滿足的邊組成的集合S；

9：在S中任意選取一條邊(u,v),并把(t,w)和(u,v)轉換成(t,v)和(u,w)；

10：如果t是奇數；

11：在圖G中任意添加一條邊(t,w)；

12：依據定理3在圖G中尋找所有滿足的邊組成的集合S；

13：在S中任意選取一條邊(u,v),并把(t,w)和(u,v)轉換成(t,v)和(u,w)；

14：t＝t+1；

15：停止并返回圖

此算法的時間復雜度為O(n³)；

所述匿名化過程的步驟6的操作實現方式為：

記錄在匿名化過程中添加和刪除的邊，記錄方式采用結構化數據庫MySQL，在MySQL數據庫中新建一個表，表結構設計如下：

邊id	前節點id	后節點id	網絡圖id	邊的類型

注：

邊id：表示新增邊的唯一編碼；

前節點id：表示新增邊的其中一個節點的唯一編碼；

后節點id：表示新增邊的另一個節點的唯一編碼；

網絡圖id：表示新增邊屬于哪一個網絡圖的唯一編碼；

邊的類型：表示此次邊是添加的還是刪除的。