計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是引用拓?fù)鋵W(xué)中研究與大小，形狀無(wú)關(guān)的點(diǎn)，線關(guān)系的方法。把網(wǎng)絡(luò)中的計(jì)算機(jī)和通信設(shè)備抽象為一個(gè)點(diǎn)，把傳輸介質(zhì)抽象為一條線，由點(diǎn)和線組成的幾何圖形就是計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)反映出網(wǎng)中各實(shí)體的結(jié)構(gòu)關(guān)系，是建設(shè)計(jì)算機(jī)網(wǎng)絡(luò)的步，是實(shí)現(xiàn)各種網(wǎng)絡(luò)協(xié)議的基礎(chǔ)，它對(duì)網(wǎng)絡(luò)的性能，系統(tǒng)的可靠性與通信費(fèi)用都有重大影響。指連接各結(jié)點(diǎn)的形式與方法。 把網(wǎng)絡(luò)中的工作站和服務(wù)器等網(wǎng)絡(luò)單元抽象為"點(diǎn)". 網(wǎng)絡(luò)中的電纜等抽象為"線". 影響網(wǎng)絡(luò)性能、系統(tǒng)可靠性、通信費(fèi)用 ① 總線拓?fù)浣Y(jié)構(gòu) 是將網(wǎng)絡(luò)中的所有設(shè)備通過(guò)相應(yīng)的硬件接口直接連接到公共總線上，結(jié)點(diǎn)之間按廣播方式通信，一個(gè)結(jié)點(diǎn)發(fā)出的信息，總線上的其它結(jié)點(diǎn)均可"收聽(tīng)"到。 優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單、布線容易、可靠性較高，易于擴(kuò)充，是局域網(wǎng)常采用的拓?fù)浣Y(jié)構(gòu)。缺點(diǎn)：所有的數(shù)據(jù)都需經(jīng)過(guò)總線傳送，總線成為整個(gè)網(wǎng)絡(luò)的瓶頸；出現(xiàn)故障診斷較為困難。著名的總線拓?fù)浣Y(jié)構(gòu)是以太網(wǎng)（Ethernet）。

　　網(wǎng)狀型拓?fù)浣Y(jié)構(gòu)：將多個(gè)子網(wǎng)或多個(gè)網(wǎng)絡(luò)連接起來(lái)構(gòu)成網(wǎng)際拓?fù)浣Y(jié)構(gòu)。在一個(gè)子網(wǎng)中，集線器、中繼器將多個(gè)設(shè)備連接起來(lái)，而橋接器、路由器及網(wǎng)關(guān)則將子網(wǎng)連接起來(lái)。根據(jù)組網(wǎng)硬件不同，主要有三種網(wǎng)際拓?fù)洌壕W(wǎng)狀網(wǎng)：在一個(gè)大的區(qū)域內(nèi)，用無(wú)線電通信鏈路連接一個(gè)大型網(wǎng)絡(luò)時(shí)，網(wǎng)狀網(wǎng)是的拓?fù)浣Y(jié)構(gòu)。通過(guò)路由器與路由器相連，可讓網(wǎng)絡(luò)選擇一條快的路徑傳送數(shù)據(jù)。主干網(wǎng)：通過(guò)橋接器與路由器把不同的子網(wǎng)或LAN連接起來(lái)形成單個(gè)總線或環(huán)型拓?fù)浣Y(jié)構(gòu)，這種網(wǎng)通常采用光纖做主干線。星狀相連網(wǎng)：利用一些叫做超級(jí)集線器的設(shè)備將網(wǎng)絡(luò)連接起來(lái)，由于星型結(jié)構(gòu)的特點(diǎn)，網(wǎng)絡(luò)中任一處的故障都可容易查找并修復(fù)。

　　網(wǎng)狀拓?fù)涞膬?yōu)點(diǎn)：（1） 網(wǎng)絡(luò)可靠性高，一般通信子網(wǎng)中任意兩個(gè)節(jié)點(diǎn)交換機(jī)之間，存在著兩條或兩條以上的通信路徑，這樣，當(dāng)一條路徑發(fā)生故障時(shí)，還可以通過(guò)另一條路徑把信息送至節(jié)點(diǎn)交換機(jī)。（2） 網(wǎng)絡(luò)可組建成各種形狀，采用多種通信信道，多種傳輸速率。（3） 網(wǎng)內(nèi)節(jié)點(diǎn)共享資源容易。（4） 可改善線路的信息流量分配。（5） 可選擇路徑，傳輸延遲小。網(wǎng)狀拓?fù)涞娜秉c(diǎn)：（1） 控制復(fù)雜，軟件復(fù)雜。2） 線路費(fèi)用高，不易擴(kuò)充。網(wǎng)狀拓?fù)浣Y(jié)構(gòu)一般用于Internet骨干網(wǎng)上，使用路由算法來(lái)計(jì)算發(fā)送數(shù)據(jù)的路徑。

　　拓?fù)淇刂茟?yīng)使網(wǎng)絡(luò)拓?fù)錆M足下列性質(zhì)中的一個(gè)或幾個(gè)：

　　連通性-為了實(shí)現(xiàn)結(jié)點(diǎn)間的互相通信，生成的拓?fù)浔仨毐ＷC連通性，即從任何一個(gè)結(jié)點(diǎn)都可以發(fā)送消息到另外一個(gè)結(jié)點(diǎn)。連通性是任何拓?fù)淇刂扑惴ǘ急仨毐ＷC的一個(gè)性質(zhì)。由UDG圖的定義可以知道，UDG圖的連通性是網(wǎng)絡(luò)能夠提供的連通性，因此一般假定UDG圖是連通的。所以，任何拓?fù)淇刂扑惴ㄉ傻耐負(fù)涠际荱DG圖的子圖。

　　對(duì)稱性-指如果從結(jié)點(diǎn)i到結(jié)點(diǎn)j有一條邊，那么一定存在從結(jié)點(diǎn)j到結(jié)點(diǎn)i的邊。由于非對(duì)稱鏈路在目前的MAC協(xié)議中沒(méi)有得到很好的支持，而且非對(duì)稱鏈路通信的開(kāi)銷(xiāo)很大，因此一般都要求生成的拓?fù)渲墟溌肥菍?duì)稱的。

　　稀疏性-指生成的拓?fù)渲械倪厰?shù)為O（n），其中n是結(jié)點(diǎn)個(gè)數(shù)。減少拓?fù)渲械倪厰?shù)可以有效減少網(wǎng)絡(luò)中的干擾，提高網(wǎng)絡(luò)的吞吐率。稀疏性還可以簡(jiǎn)化路由計(jì)算。

　　平面性-指生成的拓?fù)渲袥](méi)有兩條邊相交。由圖論可知，滿足平面性一定滿足稀疏性。地理路由協(xié)議是一種十分適合計(jì)算和存儲(chǔ)能力有限的無(wú)線傳感器結(jié)點(diǎn)的路由協(xié)議，它不需要維護(hù)路由表和進(jìn)行復(fù)雜的路由計(jì)算，只需要按照一定的規(guī)則轉(zhuǎn)發(fā)消息。但當(dāng)?shù)讓油負(fù)洳皇瞧矫鎴D時(shí)，地理路由協(xié)議不能保證消息轉(zhuǎn)發(fā)的可達(dá)性。因此，當(dāng)結(jié)點(diǎn)運(yùn)行地理路由協(xié)議時(shí)，要求生成的拓?fù)浔仨殱M足平面性。

　　結(jié)點(diǎn)度數(shù)有界-指在生成的拓?fù)渲薪Y(jié)點(diǎn)的鄰居個(gè)數(shù)小于一個(gè)常數(shù)d.降低結(jié)點(diǎn)的度數(shù)可以減少結(jié)點(diǎn)轉(zhuǎn)發(fā)消息的數(shù)量和路由計(jì)算的復(fù)雜度。

　　Spanner性質(zhì)-指在生成的拓?fù)渲腥魏蝺蓚€(gè)結(jié)點(diǎn)間的距離小于它們?cè)赨DG圖中距離的常數(shù)倍。

　　研究方法

　　目前對(duì)拓?fù)淇刂频难芯靠梢苑譃閮纱箢悺Ｒ活愂怯?jì)算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)的拓?fù)洌詽M足某些性質(zhì)。另一類是概率分析方法，在結(jié)點(diǎn)按照某種概率密度分布情況下，計(jì)算使拓?fù)湟源蟾怕蕽M足某些性質(zhì)時(shí)結(jié)點(diǎn)所需的傳輸功率和鄰居個(gè)數(shù)。

　　1.計(jì)算幾何方法

　　該方法常使用的幾何結(jié)構(gòu)有如下幾種：

　　生成樹(shù)（MST） 網(wǎng)絡(luò)拓?fù)涫且越Y(jié)點(diǎn)間的歐式距離為度量的生成樹(shù)。結(jié)點(diǎn)的傳輸半徑設(shè)為與該結(jié)點(diǎn)相鄰的長(zhǎng)邊的長(zhǎng)度。以MST為拓?fù)涞木W(wǎng)絡(luò)能保證網(wǎng)絡(luò)的連通性。由于在分布式環(huán)境下構(gòu)造MST開(kāi)銷(xiāo)巨大，一種折中的方法是結(jié)點(diǎn)采用局部MST方法設(shè)置傳輸范圍。

　　GG圖（Gabriel Graph） 在傳輸功率正比傳輸距離的平方時(shí)，GG圖是節(jié)能的拓?fù)洹ST是GG圖的子圖，GG圖也滿足連通性。

　　RNG圖（Relative Neighbor Graph） 其稀疏程度在MST和GG圖之間，連通性也在MST和GG圖之間，優(yōu)于MST,沖突干擾優(yōu)于GG圖，是兩者的折中。RNG圖易于用分布式算法構(gòu)造。

　　DT圖（Delaunay Triangulation） UDG與DT圖的交集稱為UDel圖（Unit Delaunay Triangulation）。UDel圖是稀疏的平面圖，適合于地理路由協(xié)議、節(jié)能、簡(jiǎn)化路由計(jì)算，以及降低干擾，因此十分適合作為無(wú)線底層拓?fù)洹?/P>

　　Yao Graph 研究人員提出了許多Yao Graph的變種，如在GG圖上使用Yao Graph,在Yao Graph上使用GG圖等，以減少Yao Graph中的邊數(shù)并同時(shí)保持Spanner性質(zhì)。

　　θ-Graph 與Yao Graph非常相似。不同之處在于，Yao Graph在每個(gè)扇區(qū)中選擇近的結(jié)點(diǎn)建立鏈路，而θ-Graph選擇在扇區(qū)中軸投影短的結(jié)點(diǎn)建立鏈路。

　　2.概率分析方法

　　發(fā)展成熟的隨機(jī)圖理論不適合無(wú)線傳感器網(wǎng)絡(luò)。事實(shí)上，隨機(jī)圖假設(shè)任意兩個(gè)結(jié)點(diǎn)間的邊的存在與否是互相獨(dú)立的，這一假設(shè)不符合無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)。為解決這個(gè)問(wèn)題，研究人員提出了幾何隨機(jī)圖理論。在該理論中，結(jié)點(diǎn)按照某種概率密度分布在d維區(qū)域R中。研究人員研究了這種結(jié)點(diǎn)分布下的某些性質(zhì)，諸如：到近鄰居的長(zhǎng)鏈路，歐式生成樹(shù)中長(zhǎng)邊的長(zhǎng)度，MST的總開(kāi)銷(xiāo)。近，研究人員使用幾何隨機(jī)圖理論研究無(wú)線ad hoc網(wǎng)絡(luò)的某些基本的性質(zhì)，如連通性。

　　另外兩種理論是連續(xù)滲流（continuum percolation）和占位理論（occupancy theory）。在連續(xù)滲流理論中，結(jié)點(diǎn)以Poisson密度λ分布在二維平面中，如果結(jié)點(diǎn)間距離小于r則兩個(gè)結(jié)點(diǎn)相連。已經(jīng)證明，對(duì)于λ>0,至多以大概率存在一個(gè)無(wú)限階的組件（由連通的結(jié)點(diǎn)組成的集合稱為組件，組件的階是結(jié)點(diǎn)集合中結(jié)點(diǎn)的個(gè)數(shù)）。但是，只存在一個(gè)無(wú)限階的組件不能保證網(wǎng)絡(luò)的連通性。事實(shí)上，可能存在許多（無(wú)限多）結(jié)點(diǎn)不屬于這個(gè)大組件，這樣就導(dǎo)致不連通的網(wǎng)絡(luò)通信圖。因此，連通性與屬于大組件的結(jié)點(diǎn)占所有結(jié)點(diǎn)的比例相關(guān)，這個(gè)比例又與滲流概率相關(guān)。但是，目前還沒(méi)有關(guān)于滲流概率的顯式表達(dá)式。由于連續(xù)滲流理論的模型與ad hoc的網(wǎng)絡(luò)模型相吻合，因此連續(xù)滲流理論被用于分析ad hoc網(wǎng)絡(luò)的連通性。

　　在占位理論中，假設(shè)n個(gè)球獨(dú)立地放入C個(gè)格子中。球放入格子中的放法由描述格子的某些屬性的隨機(jī)變量確定。占位理論的目標(biāo)是確定當(dāng)n和C趨近無(wú)窮時(shí)這些變量的概率分布（極限概率分布）。占位理論可以用于分析ad hoc網(wǎng)絡(luò)的連通性，可以抽象為把區(qū)域R分割成相同大小的rd個(gè)小區(qū)域（格子），確定在這種情況下每個(gè)格子中至少有一個(gè)結(jié)點(diǎn)（球）的概率。

　　概率方法研究的重要的問(wèn)題是臨界傳輸范圍（CTR）問(wèn)題，即結(jié)點(diǎn)都是同構(gòu)的，傳輸范圍相同，使網(wǎng)絡(luò)連通的傳輸范圍是多少。研究這個(gè)問(wèn)題的原因在于在無(wú)線傳感器網(wǎng)絡(luò)中廉價(jià)的無(wú)線通信部件不可能動(dòng)態(tài)調(diào)整傳輸范圍。在無(wú)線傳感器網(wǎng)絡(luò)中，只能把所有結(jié)點(diǎn)的傳輸范圍設(shè)為相同的值。減少功耗、增加網(wǎng)絡(luò)容量的惟一辦法是把傳輸范圍設(shè)為保持網(wǎng)絡(luò)連通的值。適合解決CTR問(wèn)題的概率理論是幾何隨機(jī)圖理論。因?yàn)榕R界傳輸范圍就是MST中的長(zhǎng)邊，從長(zhǎng)MST邊的概率分布中可以推導(dǎo)出CTR的概率解。但幾何隨機(jī)圖理論只適用于密集的ad hoc網(wǎng)絡(luò)。因?yàn)槔碚摷僭O(shè)放置結(jié)點(diǎn)的空間是固定的，當(dāng)結(jié)點(diǎn)個(gè)數(shù)趨于無(wú)窮時(shí)，結(jié)點(diǎn)的密度也趨于無(wú)窮。但在實(shí)際情況中，網(wǎng)絡(luò)的密度不可能很大。事實(shí)上，一個(gè)結(jié)點(diǎn)傳輸時(shí)，在它通信范圍內(nèi)的其他結(jié)點(diǎn)必須保持沉默。如果結(jié)點(diǎn)密度非常大，當(dāng)一個(gè)結(jié)點(diǎn)傳輸時(shí)，許多結(jié)點(diǎn)都必須保持沉默，將降低整個(gè)網(wǎng)絡(luò)的容量。

　　研究人員還用占位理論分析稀疏ad hoc網(wǎng)絡(luò)中保證連通性的臨界傳輸范圍問(wèn)題。

　　近年來(lái)拓?fù)淇刂萍夹g(shù)已成為研究的熱點(diǎn)，目前在這個(gè)研究領(lǐng)域中還存在著許多問(wèn)題。首先，用于建模無(wú)線傳感器網(wǎng)絡(luò)的模型過(guò)于理想化。為了得到更符合實(shí)際的量化結(jié)果，需要使用更真實(shí)的模型。其次，結(jié)點(diǎn)的分布假設(shè)過(guò)于理想化。一般的研究都假定結(jié)點(diǎn)是均勻分布的。雖然在某些情況下這種假設(shè)是合理的，但是在大多數(shù)情況下這樣的假設(shè)是過(guò)于理想化的。，安放無(wú)線傳感器的區(qū)域假設(shè)過(guò)于理想化。一般假設(shè)安放無(wú)線傳感器的區(qū)域是平坦的二維平面，沒(méi)有考慮地形的因素。