平衡k叉樹網(wǎng)絡(luò)的平均路徑長(zhǎng)度和鏈路效率

周異輝，邵志毅

（陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119）

網(wǎng)絡(luò)的平均路徑長(zhǎng)度是網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度的平均值，是網(wǎng)絡(luò)性能研究中的重要指標(biāo)［1］.對(duì)通信網(wǎng)絡(luò)而言，網(wǎng)絡(luò)的平均路徑長(zhǎng)度在一定程度上反映節(jié)點(diǎn)的信息處理能力和信息的傳遞速率.如何快速有效地計(jì)算網(wǎng)絡(luò)的平均路徑長(zhǎng)度是網(wǎng)絡(luò)研究中不可避免的問(wèn)題.文獻(xiàn)［2-5］給出不同類型網(wǎng)絡(luò)的平均路徑長(zhǎng)度.

樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，它是數(shù)據(jù)元素按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，非常類似于自然界中的樹.樹形結(jié)構(gòu)不僅為計(jì)算機(jī)應(yīng)用中常出現(xiàn)的嵌套數(shù)據(jù)提供了自然的表示，也在解決文件管理、數(shù)據(jù)庫(kù)、編譯等系統(tǒng)的算法中得到廣泛應(yīng)用.平衡k叉樹作為重要的網(wǎng)絡(luò)結(jié)構(gòu)被應(yīng)用在通信網(wǎng)和嵌入式系統(tǒng)芯片的優(yōu)化設(shè)計(jì)方案中.文獻(xiàn)［6］給出基于二叉樹表示的搜索空間數(shù)據(jù)縮減方法，文獻(xiàn)［7］介紹了基于二叉樹的有向環(huán)網(wǎng)絡(luò)的最短路徑算法，文獻(xiàn)［8］給出平衡k叉樹的離散數(shù)和完整度.本文給出n層平衡k叉樹網(wǎng)絡(luò)平均路徑長(zhǎng)度的精確計(jì)算公式，利用此公式研究平衡k叉樹網(wǎng)絡(luò)的鏈路效率，借助Matlab軟件繪圖對(duì)不同層數(shù)網(wǎng)絡(luò)的平均路徑長(zhǎng)度和鏈路效率進(jìn)行分析.

1 基本概念

首先給出平衡k叉樹、網(wǎng)絡(luò)的平均路徑長(zhǎng)度、鏈路效率等概念.

定義1［1］設(shè)k為正整數(shù)，平衡k叉樹網(wǎng)絡(luò)遞歸地定義為一個(gè)節(jié)點(diǎn)連接到k個(gè)也是k叉樹的子樹.一個(gè)節(jié)點(diǎn)稱為根節(jié)點(diǎn)，它的度為k并且連接k個(gè)子樹，后者連接到k個(gè)更多的子樹上，以此類推.這種遞歸結(jié)束于一組稱為葉子節(jié)點(diǎn)的節(jié)點(diǎn)上，葉子節(jié)點(diǎn)的度為1.所有中間節(jié)點(diǎn)經(jīng)過(guò)k＋1條鏈路連接網(wǎng)絡(luò)，因此平衡k叉樹中節(jié)點(diǎn)的度僅可能是1、k、k＋1.

注1 （1）關(guān)于平衡二叉樹的名稱，不同的文獻(xiàn)有不同的說(shuō)法，例如文獻(xiàn)［9］稱其為滿二叉樹，文獻(xiàn)［8］稱其為完全二叉樹.文獻(xiàn)［9］中的完全二叉樹與文獻(xiàn)［8］中是完全不同的概念.本文采用文獻(xiàn)［1］中的說(shuō)法，仿照其中的平衡二叉樹給出平衡k叉樹的概念.圖1中a、b、c、d分別是含有1層、2層、3層和4層的平衡二叉樹.

圖1 1～4層的平衡二叉樹Fig.1 Balanced binary tree with levels 1to 4

定義2［1］網(wǎng)絡(luò)中兩節(jié)點(diǎn)vi和vj之間經(jīng)歷邊數(shù)最少的一條簡(jiǎn)單路徑（經(jīng)歷的邊各不相同）稱為測(cè)地線.測(cè)地線的邊數(shù)dij稱為vi和vj之間的距離，或最短路徑.

定義4［1］網(wǎng)絡(luò)的鏈路效率定義為E＝1－L/M，這里M為網(wǎng)絡(luò)的鏈路數(shù)，L為網(wǎng)絡(luò)的平均路徑長(zhǎng)度.

2 平衡k叉樹網(wǎng)絡(luò)的平均路徑長(zhǎng)度和鏈路效率的計(jì)算

這里借助遞推關(guān)系給出平衡k叉樹網(wǎng)絡(luò)平均路徑長(zhǎng)度和鏈路效率的計(jì)算公式，有關(guān)遞推關(guān)系及特征方程法解遞推關(guān)系的內(nèi)容可參看文獻(xiàn)［10］.

命題1 用Yk，n表示n層平衡k叉樹網(wǎng)絡(luò)的所有節(jié)點(diǎn)與根節(jié)點(diǎn)間的距離之和，則

證明 因?yàn)閚層平衡k叉樹網(wǎng)絡(luò)的第i（1≤i≤n）層有ki－1個(gè)節(jié)點(diǎn)，到根節(jié)點(diǎn)的距離為i－1，所以

整理得

命題2 用Xk，n表示n層平衡k叉樹網(wǎng)絡(luò)的所有節(jié)點(diǎn)對(duì)之間的距離之和，則數(shù)列｛Xk，n｝n≥1滿足遞推關(guān)系

初始條件為Xk，1＝0.

證明 顯然Xk，1＝0.將n層平衡k叉樹的節(jié)點(diǎn)分為兩類:根節(jié)點(diǎn)及與根節(jié)點(diǎn)連接的k個(gè)子樹，各子樹為（n－1）層平衡k叉樹，編號(hào)依次為1，2，…，k.Xk，n為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的距離之和，包括:（1）各子樹內(nèi)部節(jié)點(diǎn)間的距離之和kXk，n－1；（2）各子樹節(jié)點(diǎn)與根節(jié)點(diǎn)的距離之和Yk，n；（3）各子樹之間節(jié)點(diǎn)對(duì)距離之和.接下來(lái)計(jì)算（3）.

由命題1，得Xk，n＝kXk，n－1＋Yk，n＋

整理得Xk，n＝kXk，n－1＋kn－1Yk，n.

由命題1可知

命題3 對(duì)于n層平衡k叉樹，

證明 用特征方程法解遞推關(guān)系:

此為1階常系數(shù)非齊次線性遞推關(guān)系，對(duì)應(yīng)的齊次遞推關(guān)系為Xk，n＝kXk，n－1，特征方程為x－k＝0，特征根為x＝k，通解為Xk，n＝Ckn.由于

所以將原遞推關(guān)系分成

對(duì)（1），k是特征根，因此設(shè)特解為＝Ankn.將其代入遞推關(guān)系（1），消去kn，得An＝A（n－1）＋.比較兩端系數(shù)，解之，得.因此

對(duì)（2），k2不是特征根，因此設(shè)特解為＝（An＋B）k2n，代入遞推關(guān)系（2），消去k2n－1，得（An＋B）k＝A（n－1）＋B＋比較兩端系數(shù)解之，得

證畢.

根據(jù)平均路徑長(zhǎng)度和鏈路效率的計(jì)算公式，有定理1n層平衡k叉樹網(wǎng)絡(luò)的平均路徑長(zhǎng)度為

鏈路效率為

3 平均路徑長(zhǎng)度和鏈路效率與網(wǎng)絡(luò)層數(shù)的關(guān)系

本節(jié)根據(jù)定理1中平均路徑長(zhǎng)度和鏈路效率的計(jì)算公式，利用Matlab軟件繪圖分析平衡k叉樹網(wǎng)絡(luò)中分叉數(shù)k和層數(shù)n對(duì)平均路徑長(zhǎng)度和鏈路效率的影響.

（1）圖2給出平衡2叉、6叉、10叉樹網(wǎng)絡(luò)的平均路徑長(zhǎng)度.從圖中可以看出，對(duì)同一個(gè)k值，平均路徑長(zhǎng)度關(guān)于層數(shù)n是增函數(shù)；對(duì)同一個(gè)n值，平均路徑長(zhǎng)度關(guān)于分叉數(shù)k是增函數(shù).

圖2 平衡k叉樹網(wǎng)絡(luò)的平均路徑長(zhǎng)度Fig.2 Average path length of balanced k-ary tree

圖3 平衡k叉樹網(wǎng)絡(luò)中平均路徑長(zhǎng)度與層數(shù)的近似線性關(guān)系Fig.3 The approximate linear relation of average path length and level number of balanced k-ary tree

（3）圖4給出平衡2叉、6叉、10叉樹網(wǎng)絡(luò)的鏈路效率.從圖中可以看出，對(duì)同一個(gè)k值，平均路徑長(zhǎng)度關(guān)于層數(shù)n是增函數(shù)，且n趨于無(wú)窮大時(shí)，鏈路效率趨近于1.

通過(guò)以上分析（1）和（3）可知，為了取得較小平均路徑長(zhǎng)度和較高的鏈路效率，k和n的值取得越大越好.但（2）表明，當(dāng)k達(dá)到一定值時(shí)，取值再增加不會(huì)導(dǎo)致平均路徑長(zhǎng)度的過(guò)多增長(zhǎng)和鏈路效率的大幅提高，因此k不需要選得過(guò)大.

圖4 平衡k叉樹網(wǎng)絡(luò)的鏈路效率Fig.4 Link efficiency of balanced k-ary tree

4 結(jié)語(yǔ)

本文通過(guò)對(duì)平衡k叉樹網(wǎng)絡(luò)進(jìn)行深入分析，得到n層平衡k叉樹網(wǎng)絡(luò)中平均路徑長(zhǎng)度和鏈路效率的精確計(jì)算公式.根據(jù)計(jì)算公式，結(jié)合數(shù)學(xué)軟件Matlab繪圖，分析了網(wǎng)絡(luò)層數(shù)的變化對(duì)平均路徑長(zhǎng)度和鏈路效率的影響.平均路徑長(zhǎng)度是網(wǎng)絡(luò)層數(shù)n的增函數(shù)，且可用線性函數(shù)近似表示；鏈路效率也隨網(wǎng)絡(luò)層數(shù)n的增加而增加.

［1］Ted G Lewis.Network science:Theory and applications［M］.New Jersey:John Wiley and Sons，2009:70-85.

［2］何宇，趙洪利，姚曜，等.介數(shù)中心性和平均路徑長(zhǎng)度整合近似算法［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（3）:44-53.

［3］董迎飛，王鼎興，鄭緯民.精確計(jì)算n維Mesh網(wǎng)絡(luò)和n維Torus網(wǎng)絡(luò)的平均路徑長(zhǎng)度［J］.計(jì)算機(jī)學(xué)報(bào)，1997，20（4）:376-379.

［4］陳浩，孫建華，金海.對(duì)等網(wǎng)絡(luò)中平均路徑長(zhǎng)度的分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，2006，27（3）:407-411.

［5］李瀛，山秀明，任勇.具有冪律度分布的因特網(wǎng)平均路徑長(zhǎng)度估計(jì)［J］.物理學(xué)報(bào)，2004，53（11）:3695-3700.

［6］邵楠，周雁舟，惠文濤，等.基于二叉樹搜索空間縮減的測(cè)試數(shù)據(jù)生成［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（1）:188-191.

［7］陳業(yè)斌.基于二叉樹的有向雙環(huán)網(wǎng)絡(luò)的最短路徑算法［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2009，37（4）:78-81.

［8］李銀奎，段寶榮，陳忠.完全k叉樹的離散數(shù)和完整度［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011，27（3）:285-291.

［9］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）［M］.北京:清華大學(xué)出版社，2011:118-155.

［10］盧開澄，盧華明.組合數(shù)學(xué)［M］.北京:清華大學(xué)出版社，2006:54-67.