移動社會網絡路由容錯理論

第1章 網絡額外連通度評估 .................................................................................................... 1
1.1 背景及相關工作 ........................................................................................................... 2
1.2 額外連通度相關定義 ................................................................................................... 2
1.3 分裂星圖網絡的額外連通度 ....................................................................................... 3
1.3.1 分裂星圖網絡定義 ........................................................................................... 3
1.3.2 分裂星圖網絡容錯性質 ................................................................................... 5
1.3.3 分裂星圖網絡的{1,2,3}-額外連通度計算 .................................................... 11
1.4 基於排列圖網絡的額外連通度 ................................................................................. 14
1.4.1 排列圖網絡定義 ............................................................................................. 14
1.4.2 排列圖網絡容錯性質 ..................................................................................... 15
1.4.3 排列圖網絡的{1,2,3}-額外連通度計算 ........................................................ 16
1.5 基於交錯群網絡的額外連通度 ................................................................................. 39
1.5.1 交錯群圖網絡定義 ......................................................................................... 39
1.5.2 交錯群圖網絡容錯性質 ................................................................................. 41
1.5.3 交錯群圖網絡的{1,2,3}-額外連通度計算 .................................................... 48
1.6 本章小結 ..................................................................................................................... 50
參考文獻 .............................................................................................................................. 50
第2章 網絡好鄰居連通度評估 ............................................................................................... 54
2.1 背景及相關工作 ......................................................................................................... 55
2.2 好鄰居連通度的相關定義 ......................................................................................... 56
2.3 分裂星圖網絡的好鄰居連通度 ................................................................................. 56
2.3.1 分裂星圖網絡的1-好鄰居連通度的計算 ..................................................... 56
2.3.2 分裂星圖網絡的2-好鄰居連通度計算 ........................................................ 56
2.3.3 分裂星圖網絡的3-好鄰居連通度計算 ........................................................ 60
2.4 增強超立方體網絡的好鄰居連通度 ......................................................................... 63
2.4.1 增強超立方體網絡的定義 ............................................................................. 63
2.4.2 增強超立方體網絡的線性多故障分析性質 ................................................. 64
2.4.3 增強超立方體網絡的1-好鄰居連通度計算 ................................................. 69
2.4.4 增強超立方體網絡的2-好鄰居連通度計算 ................................................. 75
2.4.5 增強超立方體網絡的3-好鄰居連通度計算 ................................................. 81
2.5 本章小結 ..................................................................................................................... 93
參考文獻 .............................................................................................................................. 93
第3章 網絡分支連通度刻畫 .................................................................................................. 97
3.1 背景及相關工作 ......................................................................................................... 98
3.2 分支連通度的相關定義 ............................................................................................. 99
3.3 基於交錯群圖網絡的分支連通度 ........................................................................... 100
3.3.1 交錯群圖網絡的分支連通度的上界刻畫 ................................................... 100
3.3.2 交錯群圖網絡的分支連通度的近似下界 ................................................... 103
3.4 星圖網絡的分支連通度 ........................................................................................... 106
3.4.1 星圖網絡的定義 ........................................................................................... 106
3.4.2 星圖網絡的分支容錯性 ............................................................................... 106
3.4.3 星圖網絡的{2,3}-分支連通度刻畫 ............................................................. 115
3.4.4 星圖網絡的4-分支連通度刻畫 .................................................................. 116
3.4.5 星圖網絡的5-分支連通度刻畫 .................................................................. 117
3.5 本章小結 ................................................................................................................... 118
參考文獻 ............................................................................................................................ 118
第4章 移動社會網絡基於社會屬性的優先關系圖構建 ......................................................... 122
4.1 背景及相關工作 ....................................................................................................... 123
4.2 相關術語 ................................................................................................................... 124
4.2.1 組合網絡理論的術語 ................................................................................... 124
4.2.2 移動社會網絡模型 ....................................................................................... 124
4.3 基於社會屬性的移動社會網絡的優先關系圖 ....................................................... 125
4.3.1 基於內部社會屬性的模型假設 ................................................................... 125
4.3.2 基於社會屬性的優先級關系 ....................................................................... 125
4.3.3 { 1 , , } ( , ) m mn n k … -超立方體 .................................................................................. 126
4.3.4 優先關系圖的構建 ....................................................................................... 127
4.4 優先關系圖在不連通網絡中的應用 ....................................................................... 128
4.5 本章小結 ................................................................................................................... 130
參考文獻 ............................................................................................................................ 131
第5章 拓撲圖在移動社會網絡容錯路徑中的應用 ................................................................ 133
5.1 背景及相關工作 ....................................................................................................... 134
5.2 路由優先關系圖 ....................................................................................................... 135
5.3 數據分發路由的選擇 ............................................................................................... 135
5.3.1 路由優先關系圖的性質 ............................................................................... 135
5.3.2 基於路由優先關系圖的數據分發路由 ....................................................... 137
5.4 路由性能分析 ........................................................................................................... 141
5.4.1 理論分析 ...................................................................................................... 142
5.4.2 模擬分析 ...................................................................................................... 148
5.5 本章小結 ................................................................................................................... 154
參考文獻 ............................................................................................................................ 154
第6章 基於超立方體的可靠通信在移動社會網絡中的應用 ................................................. 157
6.1 背景及相關工作 ....................................................................................................... 158
6.2 可信關系圖定義 ....................................................................................................... 161
6.3 可信模型框架 ........................................................................................................... 163
6.4 可信度計算 ............................................................................................................... 165
6.5 可靠數據分發路由選擇 ........................................................................................... 169
6.5.1 可靠路由框架和基本思想 ........................................................................... 169
6.5.2 可靠路由算法............................................................................................... 170
6.6 場景模擬分析 ........................................................................................................... 171
6.6.1 場景假設與演化 ........................................................................................... 172
6.6.2 擴展到廣義超立方體的應用 ....................................................................... 177
6.7 本章小結 ................................................................................................................... 178
參考文獻 ............................................................................................................................ 179
第7章 網絡容錯度在通信網絡中邊權重隱私保護中的應用 ................................................. 183
7.1 背景及相關工作 ....................................................................................................... 184
7.2 基本匿名思想 ........................................................................................................... 185
7.3 基於邊權重的匿名模型 ........................................................................................... 186
7.3.1 基於Floyd 算法的抽象模型 ....................................................................... 186
7.4 場景模擬分析 ........................................................................................................... 190
7.5 本章小結 ................................................................................................................... 194
參考文獻 ............................................................................................................................ 194
第8章 全局加權社會網絡圖的匿名化 .................................................................................. 197
8.1 背景及相關工作 ....................................................................................................... 198
8.2 預備知識 ................................................................................................................... 198
8.3 匿名化方案 ............................................................................................................... 199
8.3.1 基於克魯斯卡爾算法的邊權重匿名模型 ................................................... 201
8.3.2 基於普里姆算法的邊權重匿名模型 ........................................................... 203
8.4 場景模擬分析 ........................................................................................................... 204
8.5 本章小結 ................................................................................................................... 208
參考文獻 ............................................................................................................................ 208