華中科技大學(xué)博士學(xué)位論文PAGEPAGEII基于復(fù)雜網(wǎng)絡(luò)的移動通信網(wǎng)分析與設(shè)計PAGEPAGE65摘要復(fù)雜網(wǎng)絡(luò)是控制領(lǐng)域近來研究的熱點，其實際應(yīng)用涉及的范圍也越來越廣泛。隨著通信網(wǎng)規(guī)模的不斷擴(kuò)大，大量并發(fā)的數(shù)據(jù)、信息會造成網(wǎng)絡(luò)擁塞，連鎖故障等，其后果是服務(wù)質(zhì)量受到極大影響。基于復(fù)雜網(wǎng)絡(luò)理論的移動通信網(wǎng)研究與設(shè)計是具有理論價值與實踐意義的研究主題。本文就從這兩個方面入手，從研究電信行業(yè)的移動通信網(wǎng)的組織方法和基本思路開始，然后提出基于復(fù)雜網(wǎng)絡(luò)的移動通信系統(tǒng)的擁塞控制算法，以及處理的故障控制策略和數(shù)據(jù)流通過網(wǎng)絡(luò)時的性能——網(wǎng)絡(luò)服務(wù)質(zhì)量(QualityofService)控制分析方法，研究網(wǎng)絡(luò)連鎖故障和級聯(lián)崩潰等問題，得到一些新的研究結(jié)論。主要思路是，目前所遍尋的最短路徑求解算法常會使路徑趨于經(jīng)過同一個節(jié)點，致使出現(xiàn)吐吞率下降或?qū)崟r性變差，信息量在節(jié)點處特別的集中，可以使用的性能就下降了，這樣就造成擁塞，本文選擇的角度是將路由優(yōu)化，將針對鄰域節(jié)點的搜索范圍擴(kuò)大，在對部分信息擁塞算法的基礎(chǔ)上，提高網(wǎng)絡(luò)極限承載的通信量，利用算法將負(fù)載合理分配到分集路由和復(fù)雜網(wǎng)絡(luò)上來減輕緩解擁塞。起初，從建立移動通信網(wǎng)絡(luò)故障的動態(tài)模型開始，以研究網(wǎng)絡(luò)的結(jié)構(gòu)模型與連鎖故障之間的關(guān)系為出發(fā)點，并指出網(wǎng)絡(luò)系統(tǒng)對故障的抵抗能力與其本身的結(jié)構(gòu)特性的密切相關(guān)性。目前得知的是，基于現(xiàn)在的移動通信網(wǎng)有它自己的系統(tǒng)，這個系統(tǒng)有著它自己的特性，就這個組織臨界特性來說，它主要的任務(wù)是分析，在移動通信網(wǎng)絡(luò)發(fā)生的故障，以及故障產(chǎn)生的機(jī)理。主要解決的問題是在整個通信業(yè)務(wù)最重要的環(huán)節(jié)支撐系統(tǒng)，這里最易出現(xiàn)連鎖故障，提出移動通信網(wǎng)絡(luò)的牽制控制策略。仿真結(jié)果表明了牽制控制策略是非常有效果的，將重要的節(jié)點有效的進(jìn)行控制，這樣就可以將網(wǎng)絡(luò)中的各個節(jié)點利用起來傳播動力學(xué)，這種行為的最終目的是控制整個網(wǎng)絡(luò)，相比之前在每個節(jié)點增加控制器來說更加方便，更具有實際操作意義，應(yīng)用也會更加廣泛?，F(xiàn)有的研究主要是將服務(wù)策略作為重點來研究，運用的是隊列調(diào)度方法以及將響應(yīng)時間作為基礎(chǔ)的周期調(diào)度算法。將反饋控制思想用于移動通信網(wǎng)絡(luò)，提出反饋控制策略，這個策略是在網(wǎng)絡(luò)服務(wù)性能的基礎(chǔ)上被動偵聽的，同時建立了一個監(jiān)測反饋機(jī)制下的實例模型，監(jiān)測運用移動通信網(wǎng)的特性進(jìn)行。監(jiān)控網(wǎng)絡(luò)系統(tǒng)的必要性體現(xiàn)于監(jiān)控所獲得的網(wǎng)絡(luò)服務(wù)性能參數(shù)有效的利用，可以用擁塞控制系統(tǒng)策略獲得反饋，得到整個系統(tǒng)的信息，優(yōu)化網(wǎng)絡(luò)模型，從資源分配，任務(wù)調(diào)度，網(wǎng)絡(luò)資源部署和系統(tǒng)參數(shù)配置四個劃分優(yōu)化其資源，提高服務(wù)質(zhì)量。針對服務(wù)器的性能指標(biāo)進(jìn)行了詳細(xì)的研究。并且深入的研究了吞吐率、可靠性、利用率、可利用性以及響應(yīng)時間等效率。并且在對性能研究的基礎(chǔ)之上，提出了在客戶端與服務(wù)器端兩端都添加部署請求分配器的解決方案，并且將后端的雙機(jī)熱備的方式組建成虛擬集群服務(wù)器結(jié)構(gòu)。在組建的集群服務(wù)器系統(tǒng)中，利用綜合控制的思想，把后端服務(wù)器所使用的請求分配器所使用的復(fù)雜均衡策略和請求調(diào)度優(yōu)先級策略進(jìn)行整合，這樣就能更好的控制服務(wù)質(zhì)量和使這個網(wǎng)絡(luò)系統(tǒng)負(fù)載平衡，努力提高優(yōu)先級客戶的服務(wù)質(zhì)量，將業(yè)務(wù)做的更好，保證系統(tǒng)的穩(wěn)定。最后對全文進(jìn)行歸納總結(jié)，并對移動通信網(wǎng)絡(luò)進(jìn)一步的研究和發(fā)展方向進(jìn)行展望。關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)，移動通信網(wǎng)，擁塞控制，監(jiān)測與反饋，服務(wù)質(zhì)量

AbstractComplexnetworkisoneofthemainresearchtopicsfromthecontrolcommunityrecently,anditsapplicationareaextendssignificantly.ThevastconcurrentdatainlargescalecommunicationsnetworkoftenresultincongestionwhichsubsequentlybringsdowntheQualityofService(QoS).Thisthesis,basedonpreviousworksoftheothers,proposestheoperatingmechanism,faultcontrolstrategyandfuzzyrelationanalysismethodofenterprisenetwork.Thecauseofnetworkcongestionisanalyzedandcongestioncontrolmethodoncomplexnetworkisstudied.Thecascadingfailureofnetworkisdiscussed.Somenewresultsaregivenastothesebasicproblems.Themainideaisthatcurrentlysearchingshortestpathalgorithmoftenmakesthepathtopassthroughthesamenode,resultingintheemergenceofthespitswallowratetodroporrealtimevariation,theamountofinformationisespeciallyfocusedontheperformanceofnodes,canbeusedonthedecline,thuscausingcongestion,thispaperchoosetheangleroutingoptimization,searchforneighbornodeexpansion,basedonpartialinformationcongestionalgorithm,improvethenetworktrafficoftheultimatebearingcapacity,theloaddistributionroutediversityandcomplexnetworktorelievecongestionbyalgorithm.Atfirst,thedynamicmodelofthemobilecommunicationnetworkfaultisestablished.Therelationbetweennetworktopologyandpropagatedfailureisstudied,whichindicatesthatthenetworkrobustnesstofailureiscloselyrelatedtoitsowntopology.Thesimilaritybetweentheevolvementofmobilecommunicationnetworkandsand-pilemodelisthebasisofsimulatingnetworkself-organizingprocessandanalyzingthefailuresource.Thisexplainswhythefailureofonenodeintelecommunicationsnetworkcauseslargescaleglobalfailure.Topreventthefailureofkeynode,prioritizingservicesandutilizing“best-efforts”mechanismarenecessary.ThethesisanalyzedhowcongestioncausespoorQoS.Thedifferentiatedservicebasedqueueschedulealgorithmandresponsetimebasedcycleschedulealgorithmsaredesigned.Thethesisappliesthefeedbackmethodtotelecommunicationsnetworkforthefirsttime.AQoScontrolstrategybasedonpassivesensingisproposedformobilecommunicationbusinesssupportsystem.Bymodelingtheperformancefeedbackmechanismandapplyingtheefficientpathmethod,thecongestionthresholdandthenetworkprocessingabilityareimproved.Thedeployedinstanceshowsthatthecongestioncontrolstrategycombinedwiththenetworkperformancemonitoring(delayordenythelowpriorityrequest)enhancethemobilecommunicationnetwork’squalityofservicesignificantly.Performanceindicatorsfortheserverhaveadetailedstudy.Andin-depthstudyofthethroughput,reliability,efficiency,availabilityandresponsetimeefficiency.Andresearchonthebasisofperformance,presentedattheclientandserver-sidedeploymentrequestdispatcheraddedatbothendsofthesolution,andwillbebackinhotstandbywaytosetupavirtualclusterserverarchitecture.Intheformationoftheclusterserversystem,theuseofintegratedcontroltheory,theback-endserverusingtherequestdispatchercomplexbalancingstrategyusedbytheschedulingpriorityoftherequeststrategiestogether,andthusachievetheoverallnetworkloadbalancingandservicequalitycontrol,high-priorityservicerequesttoprovidebetterservicequality,andensurethestabilityofthesystem.Finally,asummaryisdoneforalldiscussionsinthedissertation.Theresearchworksfurtherstudiesarepresented.KeyWords：Complexnetwork，mobilecommunicationnetwork，congestioncontrol，monitoringandfeedback，qualityofservice目錄摘要 IAbstract III1緒論 11.1引言 11.2復(fù)雜網(wǎng)絡(luò)的研究背景 21.3復(fù)雜網(wǎng)絡(luò)的應(yīng)用研究 41.4移動通信網(wǎng)的復(fù)雜性特征 61.4.1移動通信網(wǎng)的拓?fù)涮卣?71.4.2統(tǒng)計特征 91.4.3自組織臨界特征 101.5本文的研究意義與主要內(nèi)容 112基于復(fù)雜網(wǎng)絡(luò)模型的移動通信網(wǎng) 132.1引言 132.2復(fù)雜網(wǎng)絡(luò)基本統(tǒng)計參量 132.3復(fù)雜網(wǎng)絡(luò)的基本模型 162.3.1規(guī)則網(wǎng)絡(luò) 162.3.2隨機(jī)網(wǎng)絡(luò) 172.3.3小世界網(wǎng)絡(luò) 182.3.4無標(biāo)度網(wǎng)絡(luò) 182.3.4演化網(wǎng)絡(luò)模型 182.4基于復(fù)雜網(wǎng)絡(luò)模型的移動通信網(wǎng) 192.5本章小結(jié) 223移動通信網(wǎng)中基于局部可見度的擁塞控制算法 233.1引言 233.2基于局部信息的擁塞控制算法 273.3移動通信網(wǎng)中基于局部可見度的擁塞控制算法 293.4本章小結(jié) 374移動通信網(wǎng)QoS控制 384.1引言 384.2網(wǎng)絡(luò)服務(wù)質(zhì)量性能監(jiān)測與控制 394.2.1移動通信網(wǎng)性能監(jiān)控系統(tǒng)組成 394.2.2移動通信網(wǎng)性能監(jiān)控系統(tǒng)的邏輯結(jié)構(gòu) 424.2.3系統(tǒng)的拓?fù)浣Y(jié)構(gòu) 424.3網(wǎng)絡(luò)模型與路由策略 434.3.1網(wǎng)絡(luò)實例模型 434.3.2有效路徑路由策略的應(yīng)用 454.4移動通信網(wǎng)QoS反饋控制 484.4.1業(yè)務(wù)控制規(guī)則 484.4.2設(shè)計控制規(guī)則 504.4.3可實現(xiàn)性分析 514.5網(wǎng)絡(luò)服務(wù)調(diào)度策略 524.6本章小結(jié) 565總結(jié)與展望 585.1全文總結(jié) 585.2今后工作展望 59致謝 61參考文獻(xiàn) 621緒論1.1引言研究表明，大多數(shù)的存在的網(wǎng)絡(luò)不是單獨的、隨機(jī)的或者有規(guī)則的，而是在兩者中間的復(fù)雜網(wǎng)絡(luò)，比如，小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)和自組織等。廣義上可以將自然界所有與之有關(guān)的歸結(jié)在一起的復(fù)雜網(wǎng)絡(luò)系統(tǒng)定義為網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)就是大的有規(guī)模的網(wǎng)絡(luò)，包含兩個特性，一個特性是擁有復(fù)雜的動力行為，另一個特性是具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)。它也可以用其他的方式表示，比如圖形，這種圖形中包含著非常多的節(jié)點，這些節(jié)點之間聯(lián)系的方式是通過邊和邊的連接相互聯(lián)系的?，F(xiàn)在隨著人們的關(guān)注，這個領(lǐng)域開始不斷被挖掘，同時加大了對該領(lǐng)域的探索和關(guān)注度，慢慢的一些研究方向出現(xiàn)了，這里面包括一些機(jī)理和意義，是網(wǎng)絡(luò)模型以及有統(tǒng)計特性的網(wǎng)絡(luò)所具有的，還有度量網(wǎng)絡(luò)機(jī)構(gòu)的一些方法和新的網(wǎng)絡(luò)設(shè)計的方案，以及網(wǎng)絡(luò)結(jié)構(gòu)的分析和網(wǎng)絡(luò)行為的預(yù)測和對目前存在的網(wǎng)絡(luò)性能的優(yōu)化以及關(guān)于存在的復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的性質(zhì)統(tǒng)計[2]。在平時的生活中有的食物鏈結(jié)構(gòu)、社會關(guān)系以及我們常用的無線通訊網(wǎng)絡(luò)還有使用的互聯(lián)網(wǎng)絡(luò)等這些沒有一個不具備復(fù)雜網(wǎng)絡(luò)的特征。復(fù)雜網(wǎng)絡(luò)幾乎可以說它將整個現(xiàn)實社會都覆蓋了。所有的學(xué)科的科研人員在一定程度上可以說都是將復(fù)雜網(wǎng)絡(luò)作為研究對象，這也說明了這個網(wǎng)絡(luò)具有共性和特色，然后分析并找出普遍適用的方法。在研究者中，最早是由Erdós以及Renyí提出復(fù)雜網(wǎng)絡(luò)理論的，他們設(shè)計出了ER隨機(jī)圖模型，這個模型公認(rèn)是復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)理論。研究拓?fù)浣Y(jié)構(gòu)以及動力學(xué)的過程中，必須要借助這個網(wǎng)絡(luò)系統(tǒng)才能有效的解決問題[1]。在網(wǎng)絡(luò)動力學(xué)以及結(jié)構(gòu)功能特性優(yōu)化等都是常用的方法，應(yīng)用非常廣泛。復(fù)雜網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)形態(tài)是很抽象的，用來描述這種形態(tài)的表示方式是復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，這是一種顯著地特性。所有的復(fù)雜系統(tǒng)都可以運用復(fù)雜網(wǎng)絡(luò)的方式來思考解決，這種角度的思考可以增加對系統(tǒng)結(jié)構(gòu)整體的把握性。復(fù)雜網(wǎng)絡(luò)作為理論，它有很大作用，一方面發(fā)展了該領(lǐng)域的研究方向，另一方面為復(fù)雜網(wǎng)絡(luò)提供了新的研究方向和研究方法。對許多的學(xué)科都做出了巨大貢獻(xiàn)，這里包括生物以及數(shù)學(xué)還有計算機(jī)等科學(xué)在內(nèi)的諸多學(xué)科領(lǐng)域，都具有理論和應(yīng)用上的重要意義[3]。本文首先研究分析了基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計特性，在此基礎(chǔ)上，對各種網(wǎng)絡(luò)動態(tài)過程展開分析闡述，對如何實施動態(tài)行為制定了分析策略和控制方法。由于本文作者具有在移動通訊領(lǐng)域豐富的實踐工作經(jīng)驗，借鑒網(wǎng)絡(luò)結(jié)構(gòu)理論的分析方法，本文對移動通訊網(wǎng)的動態(tài)行為過程仔細(xì)的進(jìn)行了分析以及研究。并且針對兩大問題進(jìn)行了實際運用中的探索，一個是怎樣提高網(wǎng)絡(luò)的服務(wù)性能，另一個是提高實踐效應(yīng)，詳細(xì)認(rèn)真的分析研究。1.2復(fù)雜網(wǎng)絡(luò)的研究背景最近幾十年，關(guān)于復(fù)雜網(wǎng)絡(luò)的研究工作正在如火如荼的展開。研究復(fù)雜網(wǎng)絡(luò)的熱潮起源于Watts和Strogatz的工作，兩人在1998年發(fā)表了一篇論文，在Nature雜志上將小世界(Small-World)網(wǎng)絡(luò)模型引入大家的視線。Watts和Strogatz在其論文中詳細(xì)的闡述了完全規(guī)則的網(wǎng)絡(luò)和完全隨機(jī)的網(wǎng)絡(luò)之間相同與不同之處，以及前者如何轉(zhuǎn)變到后者[4]。隨后，Barabási和Albert在1999年發(fā)表了論文，論文中指出：大多數(shù)的生活中存在的復(fù)雜網(wǎng)絡(luò)它的節(jié)點分布不是之前認(rèn)知的均勻分布或者高斯分布，而是具有冪律規(guī)律的。由于Barabási和Albert二人提出復(fù)雜網(wǎng)絡(luò)的節(jié)點度沒有非常明顯的特征分布長度，但是有無標(biāo)度特征性質(zhì)的分布它又只具有冪律分布，所以說這種網(wǎng)絡(luò)也被稱為無標(biāo)度(Scale-Free)網(wǎng)絡(luò)[4]。正是由于以上四人的研究工作，近些年來，復(fù)雜網(wǎng)絡(luò)及其相關(guān)研究引起了眾多科研工作者的持續(xù)關(guān)注[6-10]。復(fù)雜網(wǎng)絡(luò)是由大量節(jié)點通過它們之間的邊相互連接而成的一種圖結(jié)構(gòu)，它是一種有著動力行為以及復(fù)雜拓?fù)浣Y(jié)構(gòu)的大規(guī)模的網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)從動力學(xué)的角度分析，復(fù)雜網(wǎng)絡(luò)節(jié)點是這個系統(tǒng)的基本單元，可以說凡是具有一定信息和特定動力學(xué)性質(zhì)的系統(tǒng)都是由它構(gòu)成的，這些基本單元之間的聯(lián)系就是依靠鏈接或者邊則。復(fù)雜網(wǎng)絡(luò)普遍存在于人類的日常生活中。比如說移動通訊網(wǎng)絡(luò)、社會關(guān)系網(wǎng)絡(luò)、Internet網(wǎng)、人與人之間的合作、WorldWideWeb（WWW）網(wǎng)絡(luò)、交通運輸網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)等等，它們都是復(fù)雜網(wǎng)絡(luò)。正是在人類的日常生活中就存在很多的復(fù)雜網(wǎng)絡(luò)，所以很多學(xué)者就開始研究復(fù)雜網(wǎng)絡(luò)，掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。我國學(xué)術(shù)界也獲得了許多有意義的成果[1][3][9]。復(fù)雜網(wǎng)絡(luò)是就是沒有標(biāo)度，有著自相似以及自組織、小世界，還有能夠吸引大部分或者全部性質(zhì)的網(wǎng)絡(luò)，這樣的網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)，一個節(jié)點隱藏起來就會出現(xiàn)高度復(fù)雜的網(wǎng)絡(luò)。接下來，將從以下幾個方面體現(xiàn)網(wǎng)絡(luò)的復(fù)雜性[9]：1）主體是中等大小數(shù)目的，體現(xiàn)出擁有很大數(shù)目的節(jié)點，也就是元素不能太少，或太多，各種各樣的特性將在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中展現(xiàn)。2）網(wǎng)絡(luò)的自適應(yīng)性以及智能性：表現(xiàn)在網(wǎng)絡(luò)的節(jié)點或連接的產(chǎn)生與消失。網(wǎng)絡(luò)系統(tǒng)中的元素和主體可以根據(jù)“環(huán)境”和信息來適時調(diào)整行為和狀態(tài)；并且有能力來調(diào)整規(guī)則，并生成新的規(guī)則。3）多樣性的連接：在網(wǎng)絡(luò)中各個節(jié)點之間的連接，權(quán)重有著互異性，而且有時候還可能存在方向性。4）凸現(xiàn)性和不穩(wěn)定性：集中的網(wǎng)絡(luò)節(jié)點，有可能屬于非線性動力學(xué)系統(tǒng)，例如隨著時間的變化節(jié)點狀態(tài)也會發(fā)生不同的復(fù)雜改變。4）節(jié)點的多樣性：從某種角度上來說網(wǎng)絡(luò)的節(jié)點可以表示任意事物。例如，復(fù)雜網(wǎng)絡(luò)節(jié)點由計算機(jī)網(wǎng)絡(luò)構(gòu)成的，可以表示孤立的某個路由器或集線器等，而交通運輸復(fù)雜網(wǎng)絡(luò)中節(jié)點可以用來表示不同地點。6）局部性規(guī)律：復(fù)雜網(wǎng)沒有中央控制，沒有哪個主體或元素知道其他的元素的狀態(tài)和規(guī)律，一般情況下會出現(xiàn)上面所說的好幾種復(fù)雜性相互影響，結(jié)果就是有更多不可預(yù)料的后果產(chǎn)生。還有就是，組成一個計算機(jī)網(wǎng)絡(luò)必須考慮這個網(wǎng)絡(luò)的進(jìn)化過程，這個過程能夠決定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。在網(wǎng)絡(luò)中有兩個節(jié)點之間在頻繁進(jìn)行數(shù)據(jù)通信時，隨之增加的就是它們之間的連接權(quán)重，而且還會在學(xué)習(xí)和記憶性能的幫助下不斷的優(yōu)化網(wǎng)絡(luò)性能。現(xiàn)如今，國內(nèi)和國外的學(xué)者們廣泛而深入的研究了各種復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特性?？蒲泄ぷ髡邆兯芯康木W(wǎng)絡(luò)多種多樣，主要涉及了：生命科學(xué)領(lǐng)域（比如，DNA和RNA網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)）、社會學(xué)領(lǐng)域（比如，團(tuán)隊合作網(wǎng)絡(luò)、漢語學(xué)網(wǎng)絡(luò)、人際關(guān)系網(wǎng)絡(luò)）、計算機(jī)科學(xué)領(lǐng)域（比如，萬維網(wǎng)、Internet、P2P、無線傳感器等網(wǎng)絡(luò)）等諸多學(xué)科領(lǐng)域的網(wǎng)絡(luò)。在這些研究中，圖論以及社會網(wǎng)絡(luò)分析方法、數(shù)據(jù)挖掘計算機(jī)處理方法、智能計算、統(tǒng)計物理學(xué)方法橫跨多個研究學(xué)科。基于復(fù)雜網(wǎng)絡(luò)的研究思路，不同領(lǐng)域的不同研究網(wǎng)絡(luò)的科研人員所負(fù)責(zé)的研究工作也是不同的，這些工作主要包括：統(tǒng)計在網(wǎng)絡(luò)演化過程中的規(guī)律以及有關(guān)網(wǎng)絡(luò)的幾何拓?fù)湫再|(zhì)和網(wǎng)絡(luò)構(gòu)成的創(chuàng)建機(jī)制，還有網(wǎng)絡(luò)模型和性質(zhì)，以及最重要的網(wǎng)絡(luò)演化行為中的動力學(xué)機(jī)制、網(wǎng)絡(luò)自身的結(jié)構(gòu)穩(wěn)定性、網(wǎng)絡(luò)通信的擁塞控制、網(wǎng)絡(luò)的故障牽制控制等一系列問題。1.3復(fù)雜網(wǎng)絡(luò)的應(yīng)用研究先前的研究主要是針對復(fù)雜網(wǎng)絡(luò)的基本理論和模型，隨著科學(xué)技術(shù)的突飛猛進(jìn)發(fā)展、多學(xué)科知識的相互融合，網(wǎng)絡(luò)無處不在，而其復(fù)雜性日益凸顯，學(xué)者們逐漸意識到各領(lǐng)域的中廣泛存在著復(fù)雜網(wǎng)絡(luò)，需要運用復(fù)雜網(wǎng)絡(luò)的理論去詮釋和研究各種網(wǎng)絡(luò)。最近，越來越多的學(xué)者投入到復(fù)雜網(wǎng)絡(luò)的應(yīng)用研究中去，將復(fù)雜網(wǎng)絡(luò)深入到實際應(yīng)用中，這樣才能保持研究的長久生命力。從目前來看，各個領(lǐng)域的網(wǎng)絡(luò)研究大部分都能采用復(fù)雜網(wǎng)絡(luò)的研究思想，復(fù)雜網(wǎng)絡(luò)的應(yīng)用研究十分廣泛。如今，科學(xué)家們已經(jīng)根據(jù)復(fù)雜網(wǎng)絡(luò)的思想去解釋傳統(tǒng)領(lǐng)域中的各種各樣的問題。比如，計算機(jī)科學(xué)領(lǐng)域的科學(xué)家們研究Internet、萬維網(wǎng)等的網(wǎng)絡(luò)結(jié)構(gòu)與動力學(xué)行為；生物學(xué)領(lǐng)域的科學(xué)家們正在嘗試運用復(fù)雜網(wǎng)絡(luò)理論來探討細(xì)胞間的信息傳遞以及新陳代謝的過程；無線通信領(lǐng)域的學(xué)者們將復(fù)雜網(wǎng)絡(luò)模型引入到無線通信網(wǎng)絡(luò)中，分析移動通信系統(tǒng)的承載數(shù)據(jù)量和阻塞率；研究經(jīng)濟(jì)學(xué)的工作者現(xiàn)在都在運用貿(mào)易網(wǎng)絡(luò)研究我們國家和其他國家以及其他國家之間的經(jīng)濟(jì)活動以及經(jīng)濟(jì)水平。（1）生物細(xì)胞網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、DNA網(wǎng)絡(luò)正在科研工作者的努力下慢慢深入，網(wǎng)絡(luò)里面的各元素之間的關(guān)系因為網(wǎng)絡(luò)優(yōu)化變得更加明顯。生物學(xué)中的網(wǎng)絡(luò)里面大多也具有復(fù)雜網(wǎng)絡(luò)的特征，就像他們都擁有無標(biāo)度網(wǎng)絡(luò)性質(zhì)等。各類生物機(jī)體中的各種網(wǎng)絡(luò)演化過程里面的幾何拓?fù)湫再|(zhì)以及演化行為中的動力學(xué)機(jī)制，它們的分析以后會更加多元化。（2）醫(yī)學(xué)在醫(yī)學(xué)上，疾病網(wǎng)絡(luò)，在這方面已經(jīng)取得了很大的的研究成果。例如，哈佛大學(xué)的癌癥系統(tǒng)生物學(xué)中心的Albert-LaszloBarabási與MarcVedal運用復(fù)雜網(wǎng)絡(luò)理論知識來防治癌癥，并且他們在臨床方面已經(jīng)取得了實質(zhì)性的進(jìn)展。由于哈佛大學(xué)的兩位學(xué)者找出了不同基因片段在癌癥疾病網(wǎng)絡(luò)中之間的一些內(nèi)部聯(lián)系，科學(xué)家們更加有信心，人類終將打敗癌癥這一頑疾。還有就是，病毒網(wǎng)絡(luò)和腦神經(jīng)元網(wǎng)絡(luò)等研究也在相繼開展。（3）計算機(jī)網(wǎng)絡(luò)一些有關(guān)領(lǐng)域的科研工作者正在研究計算機(jī)網(wǎng)絡(luò)的一些特有性質(zhì)，而且打算將其應(yīng)用到其他方面，包含軟件設(shè)計以及信息安全好網(wǎng)絡(luò)分析等幾個方面。這個領(lǐng)域的論文數(shù)量最近幾年增長速度很快。（4）無線通信隨著無線通信技術(shù)的發(fā)展，無線通信網(wǎng)絡(luò)已經(jīng)與人類的日常生活息息相關(guān)。相關(guān)領(lǐng)域的科研工作者在各種無線通信網(wǎng)絡(luò)中，運用復(fù)雜網(wǎng)絡(luò)的理論，去解釋無線網(wǎng)的固有的特性。比如，在無線傳感器網(wǎng)絡(luò)和蜂窩移動通信網(wǎng)絡(luò)中，學(xué)者們使用復(fù)雜網(wǎng)絡(luò)來描述其網(wǎng)絡(luò)模型的建立、通信狀態(tài)的動力學(xué)行為、路由信息的傳遞以及網(wǎng)絡(luò)的負(fù)載等問題。（4）社會學(xué)由于人類社會的多元性、復(fù)雜性以及交互性，現(xiàn)實與虛擬的社交網(wǎng)絡(luò)、新聞傳播網(wǎng)絡(luò)等廣泛而深入的融入人類社會，這令社會學(xué)與復(fù)雜網(wǎng)絡(luò)的研究具有更多的交叉點?，F(xiàn)在，許多社會學(xué)領(lǐng)域的學(xué)者逐漸將研究重點轉(zhuǎn)入到復(fù)雜網(wǎng)絡(luò)的研究中，與此同時眾多復(fù)雜網(wǎng)絡(luò)的學(xué)者也進(jìn)入到社會學(xué)的領(lǐng)域中。（6）商業(yè)領(lǐng)域在商業(yè)領(lǐng)域，復(fù)雜網(wǎng)絡(luò)的研究也同樣熱門。國外幾所著名的大學(xué)進(jìn)行了合作，深入的對美國生物技術(shù)產(chǎn)業(yè)聯(lián)盟網(wǎng)絡(luò)的形成開展了研究，在研究中發(fā)現(xiàn)一些特定的集散節(jié)點是存在的，就像Genentech、Chiron這些公司。這些公司和其它公司進(jìn)行比較，它們所擁有的合作關(guān)系的數(shù)量是龐大的。在這之后，意大利也有學(xué)者對此感興趣，對這種類型的商業(yè)網(wǎng)絡(luò)進(jìn)行了更深層次的研究，他們利用錫耶納大學(xué)的制藥工業(yè)數(shù)據(jù)庫所提供的信息，研究結(jié)論，這幾所學(xué)校：加州大學(xué)歐文分校的R，White與斯坦福大學(xué)的W，Powell這些人發(fā)現(xiàn)的那些集散節(jié)點，也是屬于一種無標(biāo)度復(fù)雜網(wǎng)絡(luò)。（7）其它領(lǐng)域除了上述生物、醫(yī)學(xué)、計算機(jī)科學(xué)、無線通信、社會學(xué)以及商業(yè)等領(lǐng)域，復(fù)雜網(wǎng)絡(luò)還在經(jīng)濟(jì)數(shù)據(jù)分析[11]以及數(shù)據(jù)挖掘[12]和軟件工程[13]還有機(jī)械設(shè)計[13]等其它許多領(lǐng)域里面都得到了大多數(shù)人持續(xù)的關(guān)注。1.4移動通信網(wǎng)的復(fù)雜性特征大中型企業(yè)的網(wǎng)絡(luò)系統(tǒng)的特點包括以下幾點:信息集中化，規(guī)模龐大，結(jié)構(gòu)分散，移動公司的綜合應(yīng)用平臺就是這類網(wǎng)絡(luò)系統(tǒng)。在系統(tǒng)繁忙的時候怎樣給各種不同的業(yè)務(wù)分配資源，管理和優(yōu)化目標(biāo)已從滿足網(wǎng)絡(luò)的需求轉(zhuǎn)為滿足應(yīng)用的需求。移動通信網(wǎng)系統(tǒng)的重要特點是分布式，它們不再孤立地存在。移動通信網(wǎng)系統(tǒng)的子系統(tǒng)往往分布在不同的服務(wù)器和子網(wǎng)上，被不同的企業(yè)系統(tǒng)軟件調(diào)用。其數(shù)據(jù)和操作可在企業(yè)環(huán)境下實現(xiàn)共享，并在不同企業(yè)應(yīng)用系統(tǒng)之間基于一定的規(guī)則相互關(guān)聯(lián)，使企業(yè)內(nèi)部的資源得到充分利用，提高工作和管理效率，降低企業(yè)運營成本。移動公司的運作和運營支撐都依賴著計算機(jī)網(wǎng)絡(luò)，其業(yè)務(wù)運營及辦公管理系統(tǒng)構(gòu)成了典型的分布式企業(yè)網(wǎng)絡(luò)系統(tǒng)。為穩(wěn)定應(yīng)用網(wǎng)絡(luò)系統(tǒng)運行，加入了監(jiān)測性能的軟件，例如加入在企業(yè)信息網(wǎng)的CA（企業(yè)信息管理系統(tǒng)）和部署在BOSS（BusinessOperationSupportSystem）系統(tǒng)的TIVOLI（IBM系統(tǒng)性能監(jiān)測軟件）。在檢測到系統(tǒng)超負(fù)荷運行后，只能顯示這些數(shù)據(jù)，像那些負(fù)荷超標(biāo)的，解決的辦法只有通過擴(kuò)大系統(tǒng)容量或者是升級系統(tǒng)，現(xiàn)在缺少有效的策略手段使系統(tǒng)負(fù)荷降低。系統(tǒng)升級為滿足業(yè)務(wù)系統(tǒng)發(fā)展的需要而不斷開展，但是由于業(yè)務(wù)不斷增多，資源就顯得相對不足。甚至剛升級半年多的硬件資源就已經(jīng)落伍，這必然帶來系統(tǒng)服務(wù)性能相對變差，傳統(tǒng)的處理負(fù)荷超標(biāo)的方法，解決的辦法只有通過擴(kuò)大系統(tǒng)容量或者是升級系統(tǒng)，現(xiàn)在缺少有效的策略手段使系統(tǒng)負(fù)荷降低。更有甚者，當(dāng)大量的用戶群同步操作（如春晚短信或電話拜年）時會造成通訊網(wǎng)絡(luò)嚴(yán)重阻塞，甚至崩潰。在這些突發(fā)性“災(zāi)難”到來時，傳統(tǒng)處理負(fù)荷超標(biāo)的辦法顯得無能為力。必須借助新的理論、方法，給各種不同的業(yè)務(wù)合理分配資源，采用卓有成效的調(diào)度策略，在系統(tǒng)負(fù)載增大并出現(xiàn)危機(jī)的時候，主動地調(diào)整超負(fù)荷節(jié)點，避免崩潰故障的發(fā)生。根據(jù)復(fù)雜網(wǎng)絡(luò)的相關(guān)概念和移動通信網(wǎng)結(jié)構(gòu)特點，移動通信網(wǎng)系統(tǒng)可看成是與網(wǎng)絡(luò)、服務(wù)和應(yīng)用等多層次性能相關(guān)的復(fù)雜網(wǎng)絡(luò)。在網(wǎng)絡(luò)上監(jiān)測到系統(tǒng)的超負(fù)荷節(jié)點后，應(yīng)用連鎖故障模型，分析網(wǎng)絡(luò)結(jié)構(gòu)脆弱性與故障傳播機(jī)理的關(guān)系，從宏觀上把握網(wǎng)絡(luò)的薄弱環(huán)節(jié)，采取有效的擁塞控制措施，預(yù)防連鎖故障的發(fā)生，保證網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）。研究證明，移動通信網(wǎng)系統(tǒng)需要建立一種以業(yè)務(wù)信息獲取為先導(dǎo)，以信息傳輸分配為基礎(chǔ)，以控制業(yè)務(wù)分類、優(yōu)化服務(wù)質(zhì)量為核心，集監(jiān)測、控制、日志管理為一體的網(wǎng)絡(luò)監(jiān)測系統(tǒng)，利用所獲得的系統(tǒng)性能參數(shù)監(jiān)測系統(tǒng)的系統(tǒng)性能，對系統(tǒng)的使用性能進(jìn)行反饋控制，將快要崩潰的系統(tǒng)或變慢的系統(tǒng)進(jìn)行適當(dāng)調(diào)整，在下次硬件升級之前使系統(tǒng)能夠有效地將現(xiàn)有的資源利用起來，給用戶提供最有效的服務(wù)。1.4.1移動通信網(wǎng)的拓?fù)涮卣髟谝苿油ㄓ嵕W(wǎng)絡(luò)系統(tǒng)的各個組件是相互聯(lián)系的，他們的聯(lián)系方式通常是通過網(wǎng)頁或者通過業(yè)務(wù)方式進(jìn)行的。這些相互聯(lián)系的組建構(gòu)成了一個復(fù)雜的網(wǎng)絡(luò)。該網(wǎng)絡(luò)具有高度的關(guān)聯(lián)性和緊密性。即：緊密耦合。這種特點同時也為故障的傳播和擴(kuò)散提供了一個可乘之機(jī)。不論哪個環(huán)節(jié)出現(xiàn)了問題，都有可能借助網(wǎng)絡(luò)傳播，達(dá)到無限的擴(kuò)散，造成整個系統(tǒng)出現(xiàn)重大事故[14]。按照傳統(tǒng)的思路，基本都是先明確對比故障因果邏輯關(guān)系，然后利用先驗概率定量或者定性分析對不同形式的因果圖。如果實踐中缺乏對故障因果邏輯關(guān)系及時掌握,對分析結(jié)果就會造成影響。本章另辟蹊蹺，把移動通信網(wǎng)系統(tǒng)看做一個整體，并結(jié)合自身拓?fù)浣Y(jié)構(gòu)的特性，研究分析故障的產(chǎn)生、傳播和影響,并試圖找出故障產(chǎn)生的內(nèi)在機(jī)制和根源。營業(yè)廳終端營業(yè)廳終端營業(yè)廳終端營業(yè)廳終端應(yīng)用服務(wù)器中間件（CICS）數(shù)據(jù)庫InformixOS:Windows服務(wù)端OS:AIX接口：客服接口HLRSMP：AgentforTIVOLITIVOtherHosts監(jiān)測控制圖1.1移動通信網(wǎng)應(yīng)用系統(tǒng)結(jié)構(gòu)示意如圖1.1所示，移動公司的移動通信網(wǎng)及其業(yè)務(wù)支撐系統(tǒng)包括辦公自動化系統(tǒng)（OA系統(tǒng)）、互聯(lián)網(wǎng)訪問系統(tǒng)、財務(wù)系統(tǒng)、客服系統(tǒng)、計費系統(tǒng)、運營支撐系統(tǒng)（BOSS）、網(wǎng)絡(luò)管理系統(tǒng)等。這些企業(yè)應(yīng)用系統(tǒng)的子系統(tǒng)不是孤立地存在，往往分布在不同的服務(wù)器和子網(wǎng)上，并可以被不同的企業(yè)系統(tǒng)軟件調(diào)用。其數(shù)據(jù)和操作可在移動通信網(wǎng)絡(luò)環(huán)境下實現(xiàn)共享，并在不同企業(yè)應(yīng)用系統(tǒng)之間基于一定的規(guī)則相互關(guān)聯(lián)。將移動通信網(wǎng)系統(tǒng)中完成不同業(yè)務(wù)的實體資源抽象成節(jié)點，主要包含運行和使用企業(yè)應(yīng)用系統(tǒng)的主機(jī)設(shè)備、網(wǎng)絡(luò)設(shè)備、存儲設(shè)備、數(shù)據(jù)庫、中間件、應(yīng)用軟件等。將這些業(yè)務(wù)之間的依賴關(guān)系抽象成有權(quán)重和方向[14]的邊。移動通信網(wǎng)系統(tǒng)有著與復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征相同的內(nèi)部結(jié)構(gòu)。我們?yōu)榻鉀Q三維空間出現(xiàn)視覺盲點問題，運用投影轉(zhuǎn)移，將三維投影到二維平面得到了更加清晰的實體關(guān)系圖。其方法和構(gòu)造規(guī)則如下[7]：規(guī)則1：把實體單元關(guān)系用邊的概念進(jìn)行描述。把實體單元用節(jié)點的概念進(jìn)行描述，并且沒有考慮到邊的權(quán)重以及實際個體之間的差異；規(guī)則2：假設(shè)任意兩個節(jié)點間必須流通信息流，那么必須都采用無向連邊操作。全部將邊的權(quán)值定位1。通過以上方法構(gòu)造的復(fù)雜系統(tǒng)拓?fù)淠Ｐ途哂卸S網(wǎng)絡(luò)的特征。采用等價轉(zhuǎn)換計算深入分析拓?fù)淠Ｐ偷木W(wǎng)絡(luò)性質(zhì)，該計算方法采用鄰接矩陣的形式，計算過程如下：N表示全部節(jié)點數(shù)量，則矩陣N×N就可以表示為拓?fù)淠Ｐ?，Mij為矩陣元，節(jié)點i的度k代表距離該節(jié)點是1的節(jié)點數(shù)。其值的不同變化代表了節(jié)點與節(jié)點是否存在直接連接。若Mij是1，則代表存在，為0則代表不存在，即無需考慮自環(huán)。節(jié)點數(shù)的度k轉(zhuǎn)換計算過程如下圖1.2所示。圖1.2拓?fù)淠Ｐ蛿?shù)學(xué)轉(zhuǎn)換關(guān)系示意圖1.4.2統(tǒng)計特征使用pajek網(wǎng)絡(luò)分析軟件統(tǒng)計網(wǎng)絡(luò)特征參數(shù)時，要依據(jù)原始的數(shù)據(jù)矩陣來模擬生成便于直觀的二維網(wǎng)絡(luò)拓?fù)鋱D，圖1.3即為實體系統(tǒng)所對應(yīng)的網(wǎng)絡(luò)拓?fù)鋱D[16]。圖1.3移動通信網(wǎng)應(yīng)用系統(tǒng)實體網(wǎng)絡(luò)拓?fù)鋱D（節(jié)點數(shù)為36）(1)無標(biāo)度特性分析根據(jù)上文的拓?fù)鋱D可以看出，少數(shù)節(jié)點的連接數(shù)很多，而多數(shù)節(jié)點的連接數(shù)很少是模型系統(tǒng)的顯著特點。該特點與復(fù)雜網(wǎng)絡(luò)無標(biāo)度的特性具有一致性。低一級別的業(yè)務(wù)處理單元節(jié)點度較小，原因是其涵蓋范圍僅僅對于小范圍內(nèi)或者是對上下級進(jìn)行信息傳遞，而高一級別的業(yè)務(wù)處理單元節(jié)點度高，原因是由于涵蓋范圍廣，資源內(nèi)容豐富。這里的度表示與規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)相區(qū)別的特性，也表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點連接狀況。統(tǒng)計整理實驗實體的度分布得出如圖1.4結(jié)果。圖1.4移動通信網(wǎng)應(yīng)用系統(tǒng)實體度分布圖根據(jù)圖1.4可以看出，系統(tǒng)的冪律分布顯現(xiàn)出顯著的規(guī)則。度分布曲線經(jīng)非線性最小二乘法運算，其尺度因子值為1.44，耦合效果并沒有達(dá)到系統(tǒng)信度的要求，這同時說明兩個問題，一個是系統(tǒng)無標(biāo)度程度不高，另一個是實驗數(shù)據(jù)統(tǒng)計規(guī)模偏小。(2)小世界特性分析網(wǎng)絡(luò)集聚系數(shù)與網(wǎng)絡(luò)平均路長與拓?fù)淠Ｐ拖鄬?yīng)，移動通信網(wǎng)系統(tǒng)的平均路長與集聚系數(shù)分別是4.628與0.071，其特征參數(shù)與小世界現(xiàn)象基本相同。以上計算分析，我們證明移動通信網(wǎng)應(yīng)用系統(tǒng)具備復(fù)雜網(wǎng)絡(luò)拓?fù)涞幕咎匦?，在對其系統(tǒng)行為的演進(jìn)的研究中，我們能夠充分借鑒復(fù)雜網(wǎng)絡(luò)研究理論和方法。1.4.3自組織臨界特征在移動通訊網(wǎng)絡(luò)中，從應(yīng)用層面來看，移動通信網(wǎng)系統(tǒng)的自組織臨界性使其理所當(dāng)然歸入自治網(wǎng)絡(luò)系統(tǒng)。自組織臨界性理論最早由Bak提出。它的含義是在這樣一個復(fù)雜系統(tǒng)內(nèi)，它包含著成千上萬的組元，他們之間能夠發(fā)生短程相互作用。也就是說是一類耗散的連續(xù)網(wǎng)絡(luò)系統(tǒng)。這種系統(tǒng)在特殊的情況下可以自行演化，最后產(chǎn)生一種狀態(tài)，可以稱它自組織臨界穩(wěn)態(tài)的自組織臨界態(tài)。這個臨界態(tài)通常通過冪律分布的雪崩大小反映出來。雖然在遠(yuǎn)離臨界點時，該系統(tǒng)內(nèi)部點的改變或其他局部性變動對全局不能產(chǎn)生作用，但是在自組織臨界系統(tǒng)處于臨界點且高度關(guān)聯(lián)狀態(tài)時，任何局部性的改變或者是某個點的改變會給系統(tǒng)內(nèi)的所有節(jié)點都帶來影響。以上所說的自組織臨界特性的含義，在沙堆模型理論中得到充分體現(xiàn)。如果把沙堆看做一個系統(tǒng)，假設(shè)加入沙粒之前，沙堆處于平衡狀態(tài)。隨著沙粒越來越多，沙堆會越變越陡，但還不至于出現(xiàn)崩塌現(xiàn)象。當(dāng)正好因為某一個沙粒的加入而導(dǎo)致沙堆出現(xiàn)崩落現(xiàn)象時，這就產(chǎn)生了沙堆的臨界態(tài)。沙堆臨界態(tài)的實際大小和分布規(guī)律取決于冪率的分布。以沙堆模型為例子，影響其演進(jìn)的幾個元素主要由沙堆外貌、添加沙粒、沙堆重力、雪崩組成，他們分別代表系統(tǒng)的狀態(tài)、驅(qū)使沙堆進(jìn)入臨界狀態(tài)并發(fā)生雪崩的驅(qū)動力，導(dǎo)致沙堆崩落致使沙堆向臨界態(tài)演化的緩沖力與沙堆模型發(fā)生崩落狀況，沙堆雪崩的產(chǎn)生及發(fā)展?fàn)顟B(tài)就是取決于這幾個元素的冪率分布規(guī)律。與沙堆模型系統(tǒng)類似，移動通信網(wǎng)網(wǎng)絡(luò)系統(tǒng)也具有相應(yīng)的特性。影響移動通信網(wǎng)絡(luò)系統(tǒng)演化的主要元素由各個業(yè)務(wù)處理單元的負(fù)荷容量水平、不斷增加的用戶需求量、而同時增長的數(shù)據(jù)容量和主機(jī)處理能力、移動通信網(wǎng)絡(luò)系統(tǒng)故障這幾個組成。它們分別代表了使系統(tǒng)接近臨界點導(dǎo)致故障產(chǎn)生的驅(qū)動力，使系統(tǒng)向臨界態(tài)演化的緩沖力，移動通信網(wǎng)絡(luò)系統(tǒng)的事故。這里需要注意，移動網(wǎng)絡(luò)通信系統(tǒng)不算是一種絕對的平衡，因為系統(tǒng)中的用戶總是不斷地產(chǎn)生需求，而系統(tǒng)容量則就相對不斷變小。窗口的增長在發(fā)生丟包之后，而后在基于動態(tài)平衡的控制傳輸過程中，網(wǎng)絡(luò)故障擁塞的窗口不斷平穩(wěn)增長，最終達(dá)到平穩(wěn)傳輸?shù)臓顟B(tài)。移動通信網(wǎng)系統(tǒng)的演化過程與沙堆模型行為的相似性，是模擬網(wǎng)絡(luò)的自組織演化過程、分析系統(tǒng)故障發(fā)生機(jī)理的理論基礎(chǔ)。并且，移動通信網(wǎng)系統(tǒng)的復(fù)雜特性研究說明，系統(tǒng)能夠解決故障的能力以及應(yīng)對故障的抵抗力和它自身的結(jié)構(gòu)是息息相關(guān)的，這就是故障傳播機(jī)理的理論依據(jù)。1.5本文的研究意義與主要內(nèi)容利用復(fù)雜網(wǎng)絡(luò)己有的研究成果，可以更深刻地認(rèn)識自然界和社會的復(fù)雜性，進(jìn)一步設(shè)計出具有更好特性的復(fù)雜網(wǎng)絡(luò)或者使網(wǎng)絡(luò)一直處于工作狀態(tài)，也可以說是有用的狀態(tài)。各種的網(wǎng)絡(luò)研究已經(jīng)讓我們掌握了一定的與網(wǎng)絡(luò)有關(guān)的拓?fù)浣Y(jié)構(gòu)、演化機(jī)制的統(tǒng)計規(guī)律和形成態(tài)勢及結(jié)構(gòu)模型的復(fù)雜穩(wěn)定性方方面面的知識。本文提出的復(fù)雜網(wǎng)絡(luò)的理論應(yīng)用，在網(wǎng)絡(luò)結(jié)構(gòu)研究和動力學(xué)演化模型研究的基礎(chǔ)上，整和移動通信網(wǎng)系統(tǒng)的擁塞控制算法以及負(fù)載均衡分析方法等的問題，也是復(fù)雜網(wǎng)絡(luò)研究的重要課題之一。本文重點對以下方面的內(nèi)容進(jìn)行了研究工作:對比分析復(fù)雜網(wǎng)絡(luò)和移動通信網(wǎng)相關(guān)性，指出各自優(yōu)點和不足之處及其具體實驗對象和環(huán)境；解析現(xiàn)實移動通信網(wǎng)絡(luò)中復(fù)雜網(wǎng)絡(luò)的問題，刻畫其復(fù)雜性和相關(guān)性等方面的問題；探討由于擁塞控制和服務(wù)質(zhì)量衡量指標(biāo)的不同而帶來的復(fù)雜網(wǎng)絡(luò)中網(wǎng)絡(luò)結(jié)構(gòu)脆弱性和不穩(wěn)定性的問題。全文由六章組成，章節(jié)安排如下：第一章綜述了復(fù)雜網(wǎng)絡(luò)的相關(guān)概念，較為詳細(xì)地介紹了本文應(yīng)用的基本理論，簡要描述了論文背景以及全文的研究內(nèi)容。第二章介紹了本文研究工作開展前的準(zhǔn)備工作，主要是復(fù)雜網(wǎng)絡(luò)的基本統(tǒng)計參數(shù)，復(fù)雜網(wǎng)絡(luò)中的常見模型以及這些統(tǒng)計參量在基于復(fù)雜網(wǎng)絡(luò)的通信網(wǎng)中表示的含義，揭示移動通信網(wǎng)是具有復(fù)雜網(wǎng)絡(luò)的特性與的發(fā)展規(guī)律。第三章本文介紹了一般路由算法，是在最短路徑路由算法以及擁塞的局部路由算法等這些重點掌握的算法基礎(chǔ)上，重點研究了以局部信息為基礎(chǔ)的擁塞控制算法的路由策略。第四章建立了擁塞模型，以移動通信網(wǎng)絡(luò)出現(xiàn)故障為原型，對網(wǎng)絡(luò)結(jié)構(gòu)以及連鎖故障之間的關(guān)系進(jìn)行了研究。第五章建立了實例模型，是將移動通信網(wǎng)的性能下監(jiān)測到的反饋機(jī)制作為模型研究所獲得的網(wǎng)絡(luò)服務(wù)性能參數(shù)，這些參數(shù)是通過監(jiān)控網(wǎng)絡(luò)系統(tǒng)所獲得的，反饋控制是應(yīng)用擁塞控制策略，這樣高效地將移動通信網(wǎng)系統(tǒng)的服務(wù)質(zhì)量提高了。第六章對全文作了總結(jié)，分析了一些尚未解決的難題，同時對以后的科研工作作了展望。2復(fù)雜網(wǎng)絡(luò)模型的移動通信網(wǎng)概述2.1引言移動網(wǎng)絡(luò)的網(wǎng)絡(luò)特性被研究的目的，是實現(xiàn)基于復(fù)雜網(wǎng)絡(luò)理論的移動通信網(wǎng)管理與控制的基礎(chǔ)。本章講述的是研究工作開展前所要準(zhǔn)備的有關(guān)知識，這里主要是復(fù)雜網(wǎng)絡(luò)的基本統(tǒng)計參數(shù)，復(fù)雜網(wǎng)絡(luò)中的常見模型以及這些統(tǒng)計參量在基于復(fù)雜網(wǎng)絡(luò)的通信網(wǎng)中表示的含義，揭示移動通信網(wǎng)是具有復(fù)雜網(wǎng)絡(luò)的特性與的發(fā)展規(guī)律。2.2復(fù)雜網(wǎng)絡(luò)基本統(tǒng)計參量為方便后面的分析和理解，我們先介紹復(fù)雜網(wǎng)絡(luò)基本統(tǒng)計參量。復(fù)雜網(wǎng)絡(luò)中常用的統(tǒng)計參量[19]主要有：節(jié)點度與度分布、平均路徑長度、聚集系數(shù)、介數(shù)、最大連通分支和度相關(guān)性等等，各個特征參量的定義及其幾何意義具體描述如下。1、節(jié)點度與度分布度(degree)是關(guān)于節(jié)點最簡單也是最重要的性質(zhì)。下面的定義中各個變量的含義和范圍都給出了明確的區(qū)分。像無向圖，與某一頂點連接邊的總數(shù)，就是所謂頂點的度。像有向圖，頂點的度分為兩部分，包括出度(out-degree)和入度(in-degree)，出度就是說從這個頂點出發(fā)連接別的節(jié)點的邊的總數(shù)目，入度就是說連接終止結(jié)在頂點的邊的總數(shù)目。像一般的加權(quán)網(wǎng)絡(luò)，某一節(jié)點的度可以稱之這個節(jié)點和其它全部相鄰節(jié)點的權(quán)的求和，這就是權(quán)度，即，其中為節(jié)點j的權(quán)重，為節(jié)點i與j的權(quán)重。對于非加權(quán)網(wǎng)絡(luò)，可以當(dāng)作是加權(quán)網(wǎng)絡(luò)的特例即等權(quán)網(wǎng)絡(luò)。描述網(wǎng)絡(luò)局部特性的基本參數(shù)是節(jié)點度，度分布函數(shù)反映網(wǎng)絡(luò)系統(tǒng)的宏觀統(tǒng)計特征是度分布函數(shù)。盡管一個節(jié)點的度理論上只表征了局部信息，但是度的分布卻是復(fù)雜網(wǎng)絡(luò)里面一個特別重要的統(tǒng)計特性，統(tǒng)計其他表征全局特性參數(shù)的量化數(shù)值就是利用度分布。一直以來網(wǎng)絡(luò)里面每個頂點的頂點度的分布規(guī)律都是受到重視的，一方面度分布可以標(biāo)志網(wǎng)絡(luò)的重要拓?fù)湫再|(zhì)，另一方面經(jīng)常標(biāo)志網(wǎng)絡(luò)的重要演化機(jī)制。不同網(wǎng)絡(luò)的度的分布不同，人們根據(jù)度的分布，提出了各種不同的網(wǎng)絡(luò)。2、平均路徑長度研究人員發(fā)現(xiàn)，現(xiàn)實中復(fù)雜網(wǎng)絡(luò)的平均路徑長度并沒有想象中的那樣大，而是非常的小。比方說，“六度分離實驗”，結(jié)果表明地球上任意兩個人的聯(lián)系不會超過6個，也就是全球上的數(shù)十億人組成的關(guān)系網(wǎng)絡(luò)的平均路徑長度只是6而已。這就是人們常說的“地球村”的概念了，也是“小世界”性質(zhì)最典型的代表事例。在加權(quán)無向網(wǎng)絡(luò)中，采用兩個節(jié)點之間的權(quán)的倒數(shù)作為節(jié)點之間的距離，即（W為節(jié)點間的權(quán)），節(jié)點間的權(quán)越大，則它們之間的距離就越小。兩個節(jié)點連接次數(shù)多那么再次連接的可能就性就會大。3、聚集系數(shù)如果有兩個點A、B，而B又和C點相連，于是A點和C點相連的可能性就很大。聚集系數(shù)就是衡量重要網(wǎng)絡(luò)統(tǒng)計屬性的可能性。在非加權(quán)網(wǎng)絡(luò)里面，聚集系數(shù)用下列等式來量化：，里面是節(jié)點的聚集系數(shù)，；。為了便于計算，給出的一個等價計算式：，其中，ki是節(jié)點的度，就是說經(jīng)過ki條邊和其它ki個相鄰節(jié)點相互關(guān)聯(lián)，就是說一共在他們中間有ki(ki-1)/2條邊連接。Ki個相鄰節(jié)點之間實際有的邊數(shù)Ei和總邊數(shù)ki(ki-1)/2的比就是節(jié)點i的聚集系數(shù)Ci。在加權(quán)網(wǎng)絡(luò)里面，加權(quán)聚集系數(shù)定義即：(2.1)式(1.1)中，Si為節(jié)點的權(quán)度，Ki為節(jié)點邊的條數(shù)，Wij表示節(jié)點i和j之間的權(quán)值，ai表示節(jié)點i的權(quán)值。由式(1.1)可以看出，考慮的東西很多，有這個節(jié)點周圍的節(jié)點的個數(shù)，還有各個節(jié)點的權(quán)以及節(jié)點之間的權(quán)。網(wǎng)絡(luò)集中化的程度就是聚集系數(shù)的幾何意義，是一種網(wǎng)絡(luò)內(nèi)部的聚集傾向。4、介數(shù)（betweenness）在移動通信網(wǎng)絡(luò)系統(tǒng)分析過程中，介數(shù)被用來表示或者衡量位于網(wǎng)絡(luò)里面的某一個節(jié)點對這個網(wǎng)絡(luò)系統(tǒng)的作用。假設(shè)網(wǎng)絡(luò)里面的兩個節(jié)點是以及，影響這兩個節(jié)點之間路徑大小的因素主要取決于網(wǎng)絡(luò)上通過這兩個節(jié)點中間的節(jié)點數(shù)目，節(jié)點數(shù)越多顯示這個節(jié)點越重要。頂點的介數(shù)可以表示為[21]：(2.2)式(1.2)中，節(jié)點、的最短路徑條數(shù)表示為，、之間所經(jīng)過的最短路徑數(shù)節(jié)點表示為，結(jié)合上一段我們的分析，介數(shù)的大小取決于網(wǎng)絡(luò)的同步能力。該節(jié)點越是重要則頂點的介數(shù)就越大，而相應(yīng)的同步能力就下降。4、最大連通分支分支是相互聯(lián)系的，它以子網(wǎng)絡(luò)的形式組成了整個網(wǎng)絡(luò)系統(tǒng)。如果我們把分支的連通性不能被打破稱為最大。則最大連通分支就是介數(shù)最大的分支，而該最大分支介數(shù)與整個網(wǎng)絡(luò)介數(shù)之比就是無限網(wǎng)絡(luò)時期。最大連通分支因網(wǎng)絡(luò)的不同而不同，該參數(shù)作為衡量比界定網(wǎng)絡(luò)的穩(wěn)定性[22]。6、度相關(guān)性度相關(guān)性與描述網(wǎng)絡(luò)的正負(fù)相關(guān)有關(guān)。它表示網(wǎng)絡(luò)之中各個節(jié)點之間的相互關(guān)系。如果網(wǎng)絡(luò)是正相關(guān)，則意味著該網(wǎng)絡(luò)中度數(shù)大的節(jié)點之間易于相互連接。如果網(wǎng)絡(luò)是負(fù)相關(guān)，則意味著該網(wǎng)絡(luò)中度數(shù)小的節(jié)點與度數(shù)大的節(jié)點之間相連。根據(jù)相關(guān)研究證實，的函數(shù)就是節(jié)點之間的平均度。如果網(wǎng)絡(luò)具有不相關(guān)性，則該函數(shù)數(shù)值是一個常數(shù)，如果網(wǎng)絡(luò)具有相關(guān)性，并且不論是哪一種特性，其函數(shù)數(shù)值分別是的遞增、遞減曲線。此后，關(guān)于網(wǎng)絡(luò)度相關(guān)性的理論方法進(jìn)一步被完善并得到簡化，網(wǎng)絡(luò)的度相關(guān)性可以直接通過計算頂點度的泊松相關(guān)系數(shù)得出[7]，該參數(shù)的計算公式為：(2.3)式(2.3)中，就是條邊的頂點的度，就是條邊的頂點的度，網(wǎng)絡(luò)的總邊數(shù)用表示。該公式中，的取值范圍為大于等于-1小于等于1，網(wǎng)絡(luò)正相關(guān)為大于零0時，網(wǎng)絡(luò)負(fù)相關(guān)的為小于零0時；網(wǎng)絡(luò)不相關(guān)表示等于0。2.3復(fù)雜網(wǎng)絡(luò)的基本模型復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以用圖G=(V(G),E(G))來描述，其中V(G)={v1,v2,…,vn}是圖G的頂點集合，E(G)={en=(vi,vj),vi,vj∈V(G)}是圖G的邊的集合。對于所有vi,vj∈V(G)，如果有(vi,vj)=(vj,vi)則圖G被稱為無向圖，反之稱為有向圖[23-24]。復(fù)雜網(wǎng)絡(luò)中常用的統(tǒng)計參量主要有：節(jié)點度與度分布、平均路徑長度、聚集系數(shù)、介數(shù)、最大連通分支和度相關(guān)性等等。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也就是網(wǎng)絡(luò)中基于網(wǎng)絡(luò)拓?fù)湫再|(zhì)的結(jié)構(gòu)。網(wǎng)絡(luò)拓?fù)湫再|(zhì)就是網(wǎng)絡(luò)表現(xiàn)出來的性質(zhì)，該性質(zhì)不取決于節(jié)點的具體位置和節(jié)點之間邊的具體形態(tài)這些拓?fù)浣Y(jié)構(gòu)可以表示為：2.3.1規(guī)則網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)傳統(tǒng)上看來，能夠描述系統(tǒng)各個元素之間的相互關(guān)系，一維鏈、二維平面上的歐幾里德網(wǎng)格就屬于規(guī)則網(wǎng)絡(luò)。而環(huán)狀網(wǎng)絡(luò)則是應(yīng)用最頻繁的一種網(wǎng)絡(luò)，該網(wǎng)絡(luò)由個節(jié)點構(gòu)成，所連接的各個節(jié)點都是個節(jié)點，且每個節(jié)點的度和聚集系數(shù)都相同。節(jié)點的度表示為δ函數(shù)，公式是，而節(jié)點的聚集系數(shù)公式為(2.4)在上述算式中，d和K代表網(wǎng)絡(luò)維數(shù)以及其它節(jié)點互相連接的最近節(jié)點數(shù)。在一維規(guī)則網(wǎng)絡(luò)里面，有著較大的平均路徑長度，該長度L正相關(guān)與節(jié)點數(shù)，用公式表示為。2.3.2隨機(jī)網(wǎng)絡(luò)匈牙利數(shù)學(xué)家AlfredRenyi和PaulErdos將隨機(jī)性引入網(wǎng)絡(luò)分析研究中，設(shè)計了簡稱ER的隨機(jī)網(wǎng)絡(luò)模型，如圖2.1所示。(a)24個孤立節(jié)點(b)以概率p=0.1生成的隨機(jī)圖(c)以概率p=0.24生成的隨機(jī)圖圖2.1隨機(jī)圖隨機(jī)網(wǎng)絡(luò)可以用以下2種方法來建立。第一種：N個節(jié)點組成的網(wǎng)絡(luò)圖中，邊數(shù)為C2N=N(N-1)/2，GN,g代表隨機(jī)連接g條邊而構(gòu)成的一個隨機(jī)網(wǎng)絡(luò)圖形，則通過這樣的方法構(gòu)成的網(wǎng)絡(luò)圖形共有CgN(N-1)/2種，這種網(wǎng)絡(luò)圖形同時也是概率空間，因為各個網(wǎng)絡(luò)圖形產(chǎn)生的概率是相等。第二種是：由保持不變的N節(jié)點數(shù)目、形成邊數(shù)基于任意節(jié)點對的概率為p的網(wǎng)絡(luò)形式GN,g。在這個網(wǎng)絡(luò)圖形中，邊數(shù)固定為一個隨機(jī)變量，假定公式為pN(N-1)/2。假定隨機(jī)網(wǎng)絡(luò)G0，代表了該網(wǎng)絡(luò)中的節(jié)點v1,v2,v3,…,vn和g條邊相互連接而構(gòu)成的某個隨機(jī)網(wǎng)絡(luò)，則G0的概率可以表示為2.3.3小世界網(wǎng)絡(luò)小世界網(wǎng)絡(luò)的研究熱源于人們對現(xiàn)實網(wǎng)絡(luò)尤其是社會網(wǎng)絡(luò)所具有的集群現(xiàn)象的反思和關(guān)注。最早研究該類型網(wǎng)絡(luò)的學(xué)者是Strogatz和Watts，他們研究設(shè)計出了一個小世界網(wǎng)絡(luò)模型，該模型被稱為WS模型，并且有著復(fù)雜的社會背景。在該系統(tǒng)的研究設(shè)計中，學(xué)者們大量地借鑒了現(xiàn)實生活中人們之間的人際關(guān)系，比如大多數(shù)人都有的親朋好友，少數(shù)人具有的遠(yuǎn)方朋友甚至海外親戚關(guān)系。該模型大致可以描述為由具有N個節(jié)點的環(huán)、m條邊、“長程連接”、平均路徑長度、聚集系數(shù)等元素構(gòu)成的圖形。這些元素之間是相互聯(lián)系的，具體表現(xiàn)為N個節(jié)點環(huán)環(huán)的每一個節(jié)點都與m條邊連結(jié)，接著實施基于概率p的隨機(jī)重連，表示為重連邊的長程連接方式能縮短網(wǎng)絡(luò)的平均路徑長度，盡量減少對網(wǎng)絡(luò)聚集系數(shù)產(chǎn)生的影響。參考規(guī)則網(wǎng)絡(luò)理論的WS模型，基于概率p以N個節(jié)點為原點，對網(wǎng)絡(luò)中的每一條邊實施重連，也就是將某一條邊斷開，連接網(wǎng)絡(luò)中的其他節(jié)點與邊的一端。該重連方式排除了自邊和多邊情況。這里所說的概率p指的是對網(wǎng)絡(luò)聚集系數(shù)和平均最短距離所產(chǎn)生的具體影響[26]。此后，兩位學(xué)者有對WS模型進(jìn)行了完善重新設(shè)計了一個變體模型。該模型改進(jìn)之處是在原始格上的邊保持不動的情況下，增加了位于隨機(jī)選擇的節(jié)點對之間的邊為長程連接。這一模型的好處是不容易發(fā)生在WS模型中可能出現(xiàn)的孤立簇情況而容易分析計算。至于此后產(chǎn)生的WS模型替代品，基本原理沒有變化，只是在環(huán)狀格中間添加了節(jié)點以實現(xiàn)與環(huán)狀格上節(jié)點隨機(jī)連接，由此產(chǎn)生的邊就相當(dāng)于WS模型中的“長程連接”。此后學(xué)者們深入研究后指出，小世界特性為網(wǎng)絡(luò)的一個特性，這種特性在將增加的新節(jié)點連接到足夠多的位于網(wǎng)格邊緣上的節(jié)點時呈現(xiàn)出來。2.3.4無標(biāo)度網(wǎng)絡(luò)提到無標(biāo)度網(wǎng)絡(luò)，不得不說Barabasi和Albert提出的BA無標(biāo)度網(wǎng)絡(luò)模型[27]。下文中會給出其模型。我們知道，對于隨機(jī)網(wǎng)絡(luò)而言，盡管點與點之間的連接是隨機(jī)的，但絕大多數(shù)節(jié)點的度和分布其實是差不多的。也就是說，對于度分布是泊松分布的網(wǎng)絡(luò)，很難找到比平均度分布小很多或大很多的點。經(jīng)過Barabasi等人在1998年的研究得出結(jié)論，萬維網(wǎng)的讀分布是一個“冪律分布”?；谶@樣的結(jié)構(gòu)特性，將網(wǎng)絡(luò)的增長和優(yōu)先連接特性作為基礎(chǔ)，這樣BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法如下[4],[28]：步驟1：增長：開始是從這樣的網(wǎng)絡(luò)，一個具有m0個節(jié)點的網(wǎng)絡(luò)，每一次引入一個新的節(jié)點，然后將它與m個已存在的節(jié)點相連接，這里m≤m0。步驟2：優(yōu)先連接：一個新節(jié)點和一個早就存在的節(jié)點i相連接的概率∏i和節(jié)點i的連接度ki之間的關(guān)系，如式(1.4)所示：(2.4)經(jīng)過t步之后，這種算法產(chǎn)生一個有N=t+m0個節(jié)點，mt條邊的網(wǎng)絡(luò)。無標(biāo)度網(wǎng)絡(luò)的冪律分布的度特性，更是具有了對隨機(jī)錯誤良好的忍耐性這一特點，這是比較隨機(jī)網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的結(jié)構(gòu)魯棒性發(fā)現(xiàn)的規(guī)律，但是，無標(biāo)度網(wǎng)絡(luò)也更容易受到針對較高度數(shù)的節(jié)點的目的性攻擊。2.3.4演化網(wǎng)絡(luò)模型雖然BA模型與現(xiàn)實生活網(wǎng)絡(luò)相比，仍然具有很多不足，比如具有很小的集聚系數(shù)、度分布指數(shù)只能取3（現(xiàn)實網(wǎng)絡(luò)此參數(shù)取值范圍在2到3之間）等，但是該BA模型的設(shè)計以新的視角研究了復(fù)雜系統(tǒng)，該研究工作具有開創(chuàng)意義。進(jìn)來，對于現(xiàn)實網(wǎng)絡(luò)的研究不斷深入，學(xué)者們逐漸發(fā)現(xiàn)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不僅僅受到幾個有限因素的影響，其它因素及各個因素細(xì)微的變化對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)都會產(chǎn)生影響，再者由于現(xiàn)實網(wǎng)絡(luò)自身的特性不同，各種影響因素比如老化、成本、競爭等對其所產(chǎn)生的作用也大不相同，差異很大。于是，有必要針對現(xiàn)實中不同實際情況設(shè)計不同的網(wǎng)絡(luò)模型，這就是近來作為復(fù)雜網(wǎng)絡(luò)系統(tǒng)研究熱點的網(wǎng)絡(luò)演化。2.4基于復(fù)雜網(wǎng)絡(luò)模型的移動通信網(wǎng)從本質(zhì)上看，移動通信網(wǎng)是一個典型的復(fù)雜網(wǎng)絡(luò)。首先，移動通信網(wǎng)規(guī)模大，具有復(fù)雜網(wǎng)絡(luò)大規(guī)模的特征；其次，移動通信網(wǎng)不斷的有新的節(jié)點增加進(jìn)來，具有增長性；此外，移動通信網(wǎng)還具有節(jié)點行為復(fù)雜，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時變，有向等特征。我們認(rèn)為，移動通信網(wǎng)是具有復(fù)雜網(wǎng)絡(luò)BA無標(biāo)度網(wǎng)絡(luò)特征和自身獨立特性的復(fù)雜網(wǎng)絡(luò)?；诖耍覀兲岢鋈缦聫?fù)雜網(wǎng)絡(luò)的移動通信網(wǎng)模型。移動通信網(wǎng)中的每個用戶可視為一個節(jié)點，節(jié)點之間的連接即用戶之間的移動通話。就移動通信網(wǎng)的特點來看，也有一些特征區(qū)別于傳統(tǒng)的BA無標(biāo)度網(wǎng)絡(luò)，例如通信網(wǎng)中存在用戶離開網(wǎng)絡(luò)不再與其他任何節(jié)點發(fā)生作用。利用BA模型建立移動通信網(wǎng)的模型，應(yīng)考慮如下幾個特點：網(wǎng)絡(luò)的增長性。增加性特征可用BA模型的增加方式，即新的節(jié)點會不斷的加入到網(wǎng)絡(luò)中，新加入的節(jié)點i與節(jié)點j相連的概率與節(jié)點j的度成正比： (2.7)也即，新加入的用戶，更有可能與網(wǎng)絡(luò)中較為重要，通話較多的節(jié)點連接；節(jié)點的離開。每隔一段時間，會有有一個節(jié)點以概率p離開網(wǎng)絡(luò)，p為一個大于0，小于1的隨機(jī)數(shù)。在移動通信網(wǎng)中，相當(dāng)于一個用戶退網(wǎng)；邊的增加。隨機(jī)選取一個節(jié)點，在網(wǎng)絡(luò)中增加n條新的邊，邊的一個頂點為這個隨機(jī)選取的節(jié)點；邊的減少。節(jié)點的連接會隨機(jī)的斷開并在以后不再連接。例如某用戶撥號錯誤，與另一個用戶建立了連接，之后斷掉，不再連接?；谝陨纤惴?，我們對移動通信網(wǎng)在節(jié)點數(shù)N=100，,400和1000的情形下進(jìn)行了仿真，網(wǎng)絡(luò)的度分布如圖2.2和圖2.3所示：圖2.2移動通信網(wǎng)在不同規(guī)模下節(jié)點度分布情況圖2.3移動通信網(wǎng)絡(luò)規(guī)模為N=1000時的節(jié)點度概率分布圖可以看到，節(jié)點的度服從于冪律分布。需要注意的是，由于復(fù)雜網(wǎng)絡(luò)中的平均路徑長反映的是節(jié)點之間信息流傳遞的便利程度。在BA無標(biāo)度模型中，關(guān)鍵節(jié)點成為了網(wǎng)絡(luò)中信息流傳遞的橋梁和快捷方式，對降低平均路徑長起到了顯著作用。2.4本章小結(jié)第二章介紹全文研究工作所涉及的預(yù)備知識，主要包括復(fù)雜網(wǎng)絡(luò)的基本統(tǒng)計參量，復(fù)雜網(wǎng)絡(luò)中的常見模型以及這些統(tǒng)計參量在基于復(fù)雜網(wǎng)絡(luò)的通信網(wǎng)中表示的含義，揭示移動通信網(wǎng)是具有復(fù)雜網(wǎng)絡(luò)的特性與的發(fā)展規(guī)律。

3移動通信網(wǎng)中基于局部可見度的擁塞控制算法3.1引言擁塞現(xiàn)象是指一部分分組數(shù)量太多了，然后到達(dá)通信子網(wǎng)中，這部分的網(wǎng)絡(luò)未能及時處理，造成這部分甚至是整個網(wǎng)絡(luò)工作性能的下降，嚴(yán)重的時候網(wǎng)絡(luò)通信業(yè)務(wù)也受到影響，陷入停頓，就是死鎖現(xiàn)象。這個現(xiàn)象在公路上發(fā)生交通堵塞時常碰到，當(dāng)車輛在節(jié)假日出行時，公路網(wǎng)上的車輛會大量增加，交通就會相互干擾，因為各個走向的車流會互相干擾，這樣每輛車到達(dá)目的地的時間會相對增加（即，延遲增加），甚至一段公路上的車輛由于堵塞無法前進(jìn)（即局部發(fā)生死鎖）。圖3.1擁塞示意圖網(wǎng)絡(luò)的吞吐量和在通信網(wǎng)絡(luò)里面?zhèn)鬏數(shù)臄?shù)據(jù)包的數(shù)量密切相關(guān)。當(dāng)通信子網(wǎng)絡(luò)負(fù)荷相對小時，網(wǎng)絡(luò)的吞吐量是跟著網(wǎng)絡(luò)負(fù)荷的增加呈線性增加的。當(dāng)網(wǎng)絡(luò)負(fù)荷增加到一定的值時，如果網(wǎng)絡(luò)吞吐量下降，就說明網(wǎng)絡(luò)中出現(xiàn)擁塞現(xiàn)象。在網(wǎng)絡(luò)中出現(xiàn)擁塞現(xiàn)象時，分組到達(dá)一個節(jié)點是沒有能夠用的緩沖區(qū)，所以就需要從以前的節(jié)點重新傳分組，還有就是從源節(jié)點或系統(tǒng)的源端重傳。當(dāng)擁塞更嚴(yán)重時，有相當(dāng)數(shù)量的傳輸容量和節(jié)點緩沖區(qū)都用于這種不必要的重傳。這樣使網(wǎng)絡(luò)中的有效吞吐量下降，結(jié)果是造成了一個惡性循環(huán)，讓通信子網(wǎng)的局部甚至整體都處于一個死鎖狀態(tài)，最終導(dǎo)致網(wǎng)絡(luò)吞吐量接近于零。簡而言之就是對資源需求的總和>可用資源——擁塞出現(xiàn)表示荷載超過了資源的承受能力。我們感受到，移動通信已經(jīng)是我們?nèi)粘Ｉ罾锩娌荒苋鄙俚耐ㄐ攀侄?。隨著通信網(wǎng)絡(luò)規(guī)模的擴(kuò)大，路由問題在網(wǎng)絡(luò)通信領(lǐng)域里面已經(jīng)成為一個研究熱點。大量并發(fā)的信息引起的網(wǎng)絡(luò)擁塞往往困擾著人們。研究具有復(fù)雜特征的移動通信網(wǎng)絡(luò)的路由問題，對緩解擁塞網(wǎng)絡(luò)具有一定的指導(dǎo)意義。所謂路由是從源頭將信息通過網(wǎng)絡(luò)傳到另一端結(jié)束。路由技術(shù)的組成是兩個最基本的活動，就是確定最佳路徑和信息包的傳輸。這里面，數(shù)據(jù)包的傳輸和交換是比較簡單和直接的，而路由是比較復(fù)雜的。路由算法的決定因素如下[30]：（1）靈活性（2）快速收斂（3）堅固性（4）簡潔性（4）最優(yōu)化那么，路由算法的幾種類別可以概述如下：（1）距離向量與鏈接狀態(tài)從本質(zhì)上說，距離向量算法是將所有路由器必須將路由表信息全部或部分地傳送到鄰近的節(jié)點上。而鏈路狀態(tài)算法就是將路由表的信息傳達(dá)到整個網(wǎng)絡(luò)的節(jié)點上，但是每個路由器只能傳送自身鏈路狀態(tài)的信息，當(dāng)然，這些信息是用來描述路由表。正常情況下，利用距離向量算法能夠傳遞給鄰近的路由器大量信息，而利用鏈路狀態(tài)算法只能傳遞給網(wǎng)絡(luò)部分且只有少數(shù)的更新后的信息。因此，鏈路狀態(tài)算法的收斂速度最快，更容易避免出現(xiàn)路由循環(huán)現(xiàn)象，但同時，運用鏈路狀態(tài)算法也需要耗費大量的存儲容量和較高的CPU能力，這必然需要投入更大更多資金。但一般情況下，兩種算法都可以使用。（2）域內(nèi)與域間可通過是否在域內(nèi)工作把路由器算法區(qū)分為域內(nèi)和域間算法。本質(zhì)上，這兩種算法具有不同點，因為域內(nèi)路由算法優(yōu)化成為域間路由算法的可能性不大。（3）單路徑與多路徑如果按照網(wǎng)絡(luò)協(xié)議能否支持多條路徑指向同一任務(wù)。區(qū)分為單路徑與多路徑。多路徑算法支持?jǐn)?shù)據(jù)在多條線路上傳輸待用，但是單路徑算法卻不具有此性能。因此能夠?qū)崿F(xiàn)更大的吞吐量、可靠性。（4）靜態(tài)與動態(tài)除非網(wǎng)管主動更改，靜態(tài)路由表映射將不會發(fā)生變化，這種算法只能運用于非復(fù)雜的網(wǎng)絡(luò)環(huán)境。該算法比較容易計算設(shè)計，性能及工作效率比較可靠。靜態(tài)路由算法與上個世紀(jì)主要應(yīng)用的動態(tài)路由算法是有區(qū)別的。動態(tài)算法根據(jù)接收到的網(wǎng)絡(luò)更新數(shù)據(jù)的實際情況做出判斷，如果數(shù)據(jù)顯示網(wǎng)絡(luò)改變，則重新進(jìn)行運算并將更新后信息發(fā)出。路由器接收到這些更新后的信息后，自動計算改變路由表。動態(tài)路由算法存在不足，有些地方必須借助靜態(tài)路由算法為補充。例如，所有不可路由分組的，作為去路使所有數(shù)據(jù)能夠得到處理[31]。下面就網(wǎng)絡(luò)擁塞的基本原理作如下的闡述：（一）根據(jù)控制論，擁塞控制方法分為兩類1、開環(huán)控制：開環(huán)控制方法即將關(guān)于導(dǎo)致?lián)砣囊蛩亟y(tǒng)統(tǒng)考慮到，在設(shè)計網(wǎng)絡(luò)之前，確保網(wǎng)絡(luò)工作過程中不發(fā)生擁塞。擁塞控制時，網(wǎng)絡(luò)當(dāng)前的狀態(tài)不予以考慮。圖3.2開環(huán)控制可采用流程2、閉環(huán)控制：閉環(huán)控制的基礎(chǔ)是反饋機(jī)制。以下幾種措施（即工作過程）屬于閉環(huán)控制：◆監(jiān)測系統(tǒng)檢測擁塞現(xiàn)象在何時何地發(fā)生的情況?！魧⑦@個信息發(fā)送到可以解決擁塞的地方?！魧⒕W(wǎng)絡(luò)系統(tǒng)的運行進(jìn)行調(diào)整解決擁塞問題。（二）衡量網(wǎng)絡(luò)擁塞與否◆缺乏緩沖地方造成的數(shù)據(jù)包丟失率；◆平均隊列長度；◆超時重傳數(shù)據(jù)包的數(shù)量；◆平均數(shù)據(jù)包延遲；◆數(shù)據(jù)包延遲變化（Jitter）（三）反饋方法◆向負(fù)載發(fā)生源發(fā)送一個報警包；◆數(shù)據(jù)包結(jié)構(gòu)里面保留一個位或域，用來表示擁塞的發(fā)生，如果發(fā)生擁塞，路由器將所有的輸出包給鄰居，和他們告警；◆主機(jī)或路由器主動和周期性地發(fā)送探測報告（probe），檢查是否發(fā)生擁塞。在經(jīng)典的求最短路徑的算法中，最有名的兩個是Dijkstra算法和Bellman-Ford算法[34]。這兩種算法的思路不同，但得到的結(jié)論相同。它們的已知條件都是整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和各鏈路的長度。Dijkstra最短路徑算法由Dijkstra提出。在尋求從網(wǎng)絡(luò)中的一個節(jié)點（源）到達(dá)其它每個節(jié)點的最佳路徑，Dijkstra最短路徑算法將網(wǎng)絡(luò)里面的節(jié)點分為三個部分：一是未標(biāo)記的節(jié)點，二是臨時標(biāo)記節(jié)點和，三是最短的節(jié)點路徑（永久標(biāo)記節(jié)點）。剛開始算時，源點被初始化為最短路徑節(jié)點，其它的都是未標(biāo)記的節(jié)點。算法執(zhí)行過程中，每一次從最短路徑到相鄰節(jié)點然后擴(kuò)展節(jié)點。非最短路徑節(jié)點的相鄰節(jié)點被修改為臨時標(biāo)記的節(jié)點。判斷是否更新權(quán)重后，在所有的臨時標(biāo)記節(jié)點里面，選出權(quán)值最小的節(jié)點，修改為最短路徑節(jié)點作下一次的擴(kuò)展源。然后重復(fù)前面的步驟。該算法結(jié)束時，所有的節(jié)點都是擴(kuò)展源。Dijkstra算法中要求邊的權(quán)值非負(fù)，如果遇到負(fù)權(quán)，Dijkstra算法就無法計算了，因為總可以順著“最短路徑”再穿過負(fù)權(quán)回路從而得到更小的最短路徑值，一直這樣下去總可以找到更小的最短路徑。針對邊的權(quán)值有正有負(fù)，可以采用Bellman-Ford算法。Bellman-ford算法對含有權(quán)值為負(fù)的有向圖返回一個布爾值，這個布爾值說明圖里面是否有著一個從源節(jié)點能夠到達(dá)的，權(quán)為負(fù)的回路。如果有這樣的回路的話，算法說明這個問題是沒有答案的；如果沒有這樣的回路，算法將產(chǎn)生最短路徑和它的權(quán)值。從本質(zhì)上來講，路由算法不直接產(chǎn)生網(wǎng)絡(luò)擁塞。但是路由算法效率的好快，卻能使得網(wǎng)絡(luò)擁塞的效果有顯著性的差異。即：路由算法通過影響網(wǎng)絡(luò)擁塞阻塞機(jī)制來影響網(wǎng)絡(luò)的整體效率[36-37]。在網(wǎng)絡(luò)里面有擁塞現(xiàn)象發(fā)生的時候，特別有效率的路由算法是能夠高效率的檢測到局部擁塞信息，并采取及時分散的方式將數(shù)據(jù)報文分散到其他的路由端口或者其他的路由器上，通過鏈路變更的方式來解決網(wǎng)絡(luò)擁塞。從而實現(xiàn)改善網(wǎng)絡(luò)的性能的目的，相反，如果路由算法較差，不僅局部網(wǎng)絡(luò)擁塞得不到有效的解決，同時還會加劇網(wǎng)絡(luò)擁塞的現(xiàn)象，甚至容易產(chǎn)生導(dǎo)致網(wǎng)絡(luò)崩潰。上述所研究的擁塞控制算法中，通常包括兩種常用機(jī)制。一種是擁塞控制(congestioncontrol)，另外一種是擁塞避免(congestionavoidance)，這兩種機(jī)制是不同的[39]。擁塞控制本質(zhì)上是一種“恢復(fù)”機(jī)制，它的作用是把處于阻塞狀態(tài)的網(wǎng)絡(luò)恢復(fù)過來；擁塞避免機(jī)制主要的作用是防患于未然，是一個“預(yù)防”的機(jī)制，就是防止網(wǎng)絡(luò)陷入阻塞狀態(tài)，并且保證網(wǎng)絡(luò)處于高效的運行狀態(tài)。通常情況下，帶寬容量、數(shù)據(jù)并發(fā)量以及存儲空間不足等問題都會導(dǎo)致網(wǎng)絡(luò)產(chǎn)生擁塞等問題。3.2基于局部信息的擁塞控制算法在傳輸控制協(xié)議中最基本以及最重要的組成部分就是擁塞控制技術(shù)。一個經(jīng)常有嚴(yán)重的擁塞和不能及時恢復(fù)的網(wǎng)絡(luò)是不可能實現(xiàn)良好的服務(wù)質(zhì)量保證的，所以說其他服務(wù)質(zhì)量機(jī)制正常工作的必要前提是實現(xiàn)擁塞控制。擁塞控制本質(zhì)上是一個如何共享資源的問題。這里的資源包括三點：節(jié)點處理能力和緩沖區(qū)空間以及通信鏈路帶寬。這三個其中的一個都有可能成為潛在的瓶頸。對于移動通信網(wǎng)，有著與一般復(fù)雜網(wǎng)絡(luò)不同的條件和要求，其緩存空間不大、數(shù)據(jù)處理要求高、帶寬不夠大，以及通信模式的數(shù)據(jù)流融合直接導(dǎo)致了認(rèn)證系統(tǒng)中的其他網(wǎng)絡(luò)協(xié)議是不可用的。這類算法BA模型具體描述如下[42-44]：BA模型在每一個時間步長，系統(tǒng)生成的R個數(shù)據(jù)包，隨機(jī)選擇的源節(jié)點和目的節(jié)點，都由他們發(fā)送C個數(shù)據(jù)包。當(dāng)數(shù)據(jù)包被發(fā)送時，采取的方式是相鄰的局部搜索策略。如果該數(shù)據(jù)包的目的地被發(fā)現(xiàn)在本地區(qū)域中，它將被直接傳遞到目標(biāo)。否則，數(shù)據(jù)包被發(fā)送到鄰居節(jié)點i，選取概率如公式(3.3)所示：(3.1)這里，ki為節(jié)點i的度，是一個可調(diào)參數(shù)。只要這個數(shù)據(jù)包到達(dá)目的地，它就不系統(tǒng)中。由公式(3.1)表明：當(dāng)<0時，數(shù)據(jù)包會第一個考慮相鄰節(jié)點，這樣選擇度比較小，這樣在一定程度上可以對擁塞起到緩解的作用，尤其是對度比較大的節(jié)點；當(dāng)=0時，所有相鄰節(jié)點被選擇的機(jī)會是一樣的，這時候就可以啟用隨機(jī)游走的路由算法來實現(xiàn)；當(dāng)>0時，度比較大的相鄰節(jié)點會被數(shù)據(jù)包優(yōu)先考慮，這樣的結(jié)果就是這些節(jié)點造成擁塞的概率明顯的增加了。數(shù)據(jù)包的傳遞遵循兩個重要的原則，即：（1）每個節(jié)點的等待隊列是無限大的，并且按照先進(jìn)先出的原則（FIFO）；（2）路徑重復(fù)避免原則（PathIterationAvoidance）。就是同一個數(shù)據(jù)包在一對節(jié)點中只能傳送1次。為了簡化，你可以選擇C（定義為在一個時間步長的數(shù)據(jù)包數(shù)量，每個節(jié)點可以發(fā)送到其他節(jié)點）作為節(jié)點的度K，即，C=K也可以讓C作為一個常數(shù)。在該模型中，將整個網(wǎng)絡(luò)的容量定義為網(wǎng)絡(luò)由自由狀態(tài)變?yōu)閾砣麪顟B(tài)時的系統(tǒng)數(shù)據(jù)包生成率Rc。自由態(tài)就是系統(tǒng)中某時間步生成數(shù)據(jù)包的個數(shù)和從系統(tǒng)移除的數(shù)據(jù)包個數(shù)平衡時的系統(tǒng)的狀態(tài)。當(dāng)系統(tǒng)處于擁塞狀態(tài)時，由節(jié)點產(chǎn)生的數(shù)據(jù)包慢慢地在系統(tǒng)中積累下來，只有少量的數(shù)據(jù)包到達(dá)目的地。為了準(zhǔn)確地描述從自由態(tài)向擁塞態(tài)過度的過程，引入?yún)?shù)[44]：(3.2)其中，表示在時刻t系統(tǒng)中存在的數(shù)據(jù)包的個數(shù)。明顯地，上式即為：從t時刻開始系統(tǒng)里面增加、積累的數(shù)據(jù)包個數(shù)。式(3.2)中，表示對于時間窗口求平均。對于，且，這說明系統(tǒng)是在自由狀態(tài)下的，無數(shù)據(jù)包滯留積累在網(wǎng)絡(luò)里面；而對于，（是大于0的一個常量），這說明在系統(tǒng)里面停留的數(shù)據(jù)包會累積，最終的結(jié)果是系統(tǒng)發(fā)生崩潰。3.3移動通信網(wǎng)中基于局部可見度的擁塞控制算法