• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2014-12-31 12:01:54周異輝邵志毅
      關(guān)鍵詞:二叉樹計(jì)算公式鏈路

      周異輝,邵志毅

      (陜西師范大學(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.

      猜你喜歡
      二叉樹計(jì)算公式鏈路
      家紡“全鏈路”升級(jí)
      CSP真題——二叉樹
      電機(jī)溫升計(jì)算公式的推導(dǎo)和應(yīng)用
      天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)
      二叉樹創(chuàng)建方法
      2019離職補(bǔ)償金計(jì)算公式一覽表
      一種由層次遍歷和其它遍歷構(gòu)造二叉樹的新算法
      基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用
      論復(fù)雜二叉樹的初始化算法
      河南科技(2014年24期)2014-02-27 14:20:01
      采用初等代數(shù)推導(dǎo)路基計(jì)算公式的探討
      陆丰市| 高台县| 伊川县| 巴楚县| 金坛市| 临猗县| 古田县| 婺源县| 屯昌县| 策勒县| 尚志市| 休宁县| 资溪县| 海南省| 瓮安县| 昭平县| 道孚县| 嵩明县| 顺义区| 尼木县| 宁都县| 兴安盟| 思南县| 德化县| 大安市| 温宿县| 大港区| 读书| 霍邱县| 成都市| 额尔古纳市| 章丘市| 毕节市| 梓潼县| 广南县| 东辽县| 英山县| 宝丰县| 正阳县| 岚皋县| 疏勒县|