【正文】 for c1=1:cluster1 if (C(c1).circle_id==j) min_circle_id=j。而選擇簇頭節(jié)點(diǎn)時(shí)，本算法采用拓?fù)涑跏紭?gòu)建的算法，為每個(gè)簇選擇簇頭的父節(jié)點(diǎn)，算法的主要思想是：初始拓?fù)浣⒅?，根?jù)當(dāng)前簇頭節(jié)點(diǎn)所在的位置信息，為其選擇合適的簇頭父節(jié)點(diǎn)，簇頭父節(jié)點(diǎn)可以直接與匯聚節(jié)點(diǎn)通信。分簇算法中，建立鏈路及網(wǎng)絡(luò)拓?fù)涞臅r(shí)間主要是用于選擇簇頭和簇的形成上。在某些對(duì)數(shù)據(jù)的實(shí)時(shí)性要求嚴(yán)格的場景應(yīng)用中，此情況的出現(xiàn)是十分嚴(yán)重的。可見，此類節(jié)點(diǎn)的通信中斷對(duì)其所在的簇或者整個(gè)網(wǎng)絡(luò)的影響是非常小的。當(dāng)簇內(nèi)普通節(jié)點(diǎn)的通信受到干擾或者破壞時(shí)，此節(jié)點(diǎn)可能會(huì)暫時(shí)或者永久性的通信中斷，而導(dǎo)致其監(jiān)測區(qū)域內(nèi)的數(shù)據(jù)不能被實(shí)時(shí)采集。為了保證網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)的實(shí)時(shí)性，初始拓?fù)錁?gòu)成之后，當(dāng)網(wǎng)絡(luò)中某個(gè)或者某些節(jié)點(diǎn)的通信遭到干擾或者破壞時(shí)，如何重新建立鏈路，恢復(fù)網(wǎng)絡(luò)拓?fù)涫鞘种匾膯栴}。本章設(shè)計(jì)一種基于同心圓象限的無線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)算法。所以，我們不能在這種同心圓象限劃分網(wǎng)格的基礎(chǔ)上，進(jìn)行節(jié)點(diǎn)的拓?fù)涞某跏蓟?。這種基于同心圓象限的網(wǎng)格劃分的大小不同，離圓心遠(yuǎn)的地方，劃分的環(huán)弧空間就較大。（5）扇區(qū)空間內(nèi)部的骨干節(jié)點(diǎn)可以組成樹狀鏈路等的其他子拓?fù)?，再加上原有的初始拓?fù)洌鰪?qiáng)了整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的健壯性，具有較好的連通性和容錯(cuò)性。（4）拓?fù)浣Y(jié)構(gòu)具有良好的負(fù)載均衡性。（2）在定位方面，也可以根據(jù)位置標(biāo)識(shí)進(jìn)行節(jié)點(diǎn)定位，在分布不大的網(wǎng)絡(luò)中，節(jié)點(diǎn)失效時(shí)也可以由位置標(biāo)識(shí)進(jìn)行快速恢復(fù)和連通，使得拓?fù)湟子谛迯?fù)，維護(hù)成本較低。 環(huán)弧空間示意圖將同心圓象限劃分的環(huán)弧空間應(yīng)用到無線傳感器網(wǎng)絡(luò)，分扇區(qū)的同心圓象限空間的具體網(wǎng)格為環(huán)弧空間，環(huán)弧空間的劃分使得整個(gè)區(qū)域的每個(gè)被劃分出的區(qū)域都有唯一的數(shù)字標(biāo)識(shí)，這個(gè)標(biāo)識(shí)被稱為位置標(biāo)識(shí)。，n=3,空間被劃分成8部分，也就是八象限，象限分割線為4條，然后畫出10個(gè)半徑不同的同心圓，這樣每個(gè)象限被劃分成大小不同的10個(gè)環(huán)弧空間。其次，在標(biāo)準(zhǔn)的樹和子樹結(jié)構(gòu)中，上層和下層節(jié)點(diǎn)之間的關(guān)系通常是一對(duì)多，且一般沒有同層鄰居。扇區(qū)環(huán)弧空間的思想借鑒了樹和子樹結(jié)構(gòu)的層次概念，但兩者并不相同[37]。我們把由象限分割線和相鄰兩個(gè)圓弧組成的空間部分叫做環(huán)弧空間（離原點(diǎn)最近的環(huán)弧空間是由原點(diǎn)和圓弧組成的）。先根據(jù)四象限劃分思想，把平面劃分成類象限的2n（n=1,2,3……）部分，通過原點(diǎn)劃分象限的直線叫做象限分割線，然后再以原點(diǎn)為圓心，以不同半徑劃出同心圓，空間又被分為大小不同的圓弧。而以原點(diǎn)為基準(zhǔn)，橫軸、縱軸以及兩條經(jīng)過原點(diǎn)的X型直線將平面均分為8個(gè)象限，從原點(diǎn)的的右軸基準(zhǔn)線開始，象限空間按逆時(shí)針方向劃分為8個(gè)子象限空間，再把同心圓嵌套到環(huán)弧空間里面，形成分扇區(qū)的環(huán)弧空間。GAF算法中虛擬單元格劃分和節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換機(jī)制具有一定的研究意義，但是要求節(jié)點(diǎn)精確的地理信息位置，對(duì)節(jié)點(diǎn)提出了很高的要求。處于發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)都可以競爭選簇頭。假設(shè)所有節(jié)點(diǎn)的通信半徑為 R，網(wǎng)絡(luò)區(qū)域劃分為邊長為 r 的正方形虛擬單元格，為了保證相鄰兩個(gè)單元格內(nèi)的任意兩個(gè)節(jié)點(diǎn)能夠直接通信，需要滿足如下關(guān)系式： 式31GAF算法的第二階段是簇頭節(jié)點(diǎn)的選擇。 GAF算法中虛擬單元格劃分的示意圖GAF算法的第一階段是虛擬單元格的劃分。GAF[36]（Geographical Adaptive Fidelity）算法是以節(jié)點(diǎn)地理位置為依據(jù)的分簇算法?；诰W(wǎng)格劃分的典型拓?fù)淇刂扑惴ㄓ蠫AF算法、DAEA算法等；基于網(wǎng)格劃分的典型路由協(xié)議有：GRID[33]、GLS[34]算法等。在無線傳感器網(wǎng)絡(luò)中，為了獲取有效準(zhǔn)確的監(jiān)測信息，網(wǎng)絡(luò)有時(shí)需要獲得地理信息，因此基于地理位置信息的拓?fù)淇刂?、路由協(xié)議研究也廣泛起來。第3章　基于同心圓象限劃分的簇頭拓?fù)渚S護(hù)算法第3章 基于同心圓象限劃分的簇頭拓?fù)渚S護(hù)算法拓?fù)渚S護(hù)算法是在無線傳感器網(wǎng)絡(luò)拓?fù)涑跏紭?gòu)建完畢之后的小規(guī)?；謴?fù)維護(hù)算法。 本章小結(jié)本章給出了無線傳感器網(wǎng)絡(luò)拓?fù)淇刂萍夹g(shù)的定義。（7）保持連接到基站的節(jié)點(diǎn)的數(shù)目：網(wǎng)絡(luò)的存活程度由依舊能夠和基站通信的節(jié)點(diǎn)數(shù)目決定[32]。（6）數(shù)據(jù)包收發(fā)率大幅度下降的時(shí)間，此定義估算的是直到數(shù)據(jù)包傳送率急劇下降[31]的時(shí)間。這是適用于CDS拓?fù)淇刂萍夹g(shù)的網(wǎng)絡(luò)生命周期的定義[30]。這種網(wǎng)絡(luò)生命周期的定義多用在層次型網(wǎng)絡(luò)拓?fù)?。?）少于建立骨干節(jié)點(diǎn)數(shù)目的時(shí)間：網(wǎng)絡(luò)生命周期指的是直到網(wǎng)絡(luò)缺乏骨干節(jié)點(diǎn)數(shù)目的時(shí)間[29]。（3）部分存活的節(jié)點(diǎn)：網(wǎng)絡(luò)的生命周期也可以是存活節(jié)點(diǎn)的時(shí)間函數(shù)[28]。（2）存活節(jié)點(diǎn)的數(shù)量：活著節(jié)點(diǎn)的數(shù)量作為時(shí)間的函數(shù)的[26]，來衡量網(wǎng)絡(luò)的生命周期也有重要的意義[27]。（1）第一個(gè)節(jié)點(diǎn)的死亡時(shí)間：第一個(gè)節(jié)點(diǎn)的死亡時(shí)間常常用來定義網(wǎng)絡(luò)的生命周期[25]?，F(xiàn)在學(xué)術(shù)界，網(wǎng)絡(luò)的生命周期有著許多不同的定義。仿真結(jié)果表明：WCAGSEN算法下的網(wǎng)絡(luò)中最后一個(gè)節(jié)點(diǎn)的死亡時(shí)間能夠比GSEN延長20%左右。通過仿真分析發(fā)現(xiàn)，GSEN算法在40%節(jié)點(diǎn)死亡的情況下，數(shù)據(jù)轉(zhuǎn)發(fā)性能比LEACH高30%，比PEGASIS高30%。在信息數(shù)據(jù)轉(zhuǎn)發(fā)階段，簇內(nèi)節(jié)點(diǎn)沿著簇內(nèi)鏈的方向?qū)?shù)據(jù)傳輸?shù)酱仡^，簇頭沿著另外的高級(jí)鏈將數(shù)據(jù)轉(zhuǎn)發(fā)至匯聚節(jié)點(diǎn)。在LEACH算法和PEGASIS算法的基礎(chǔ)上，文獻(xiàn)[24]結(jié)合這兩種算法的優(yōu)點(diǎn)提出了基于分簇的無線傳感器網(wǎng)絡(luò)算法GSEN（Groupbased Sensor Network）。為了使節(jié)點(diǎn)輪流與匯聚點(diǎn)間通信以均衡節(jié)點(diǎn)的能耗，第i回合的鏈?zhǔn)坠?jié)點(diǎn)為節(jié)點(diǎn)號(hào)i除以節(jié)點(diǎn)總數(shù)N的余數(shù)。協(xié)議要求在每個(gè)回合的數(shù)據(jù)采集過程中，給頂層的節(jié)點(diǎn)都想附近的鄰居發(fā)送數(shù)據(jù)，所有接收數(shù)據(jù)的節(jié)點(diǎn)被提升為上一層的節(jié)點(diǎn)。第一種方法接了信號(hào)編碼方式，如碼分多址CDMA；第二種方法只允許空間上分隔的節(jié)點(diǎn)可以同時(shí)傳輸數(shù)據(jù)。 由Lindsey等人提出的分簇PEGASIS協(xié)議是對(duì)PEGASIS的擴(kuò)展，該協(xié)議的目標(biāo)是降低數(shù)據(jù)包到匯聚點(diǎn)傳送過程中所引起的延時(shí)。對(duì)那些利用率較高的網(wǎng)絡(luò)而言，拓?fù)涞恼{(diào)整會(huì)帶來更大的能源開銷。因此節(jié)點(diǎn)很可能在同一時(shí)間內(nèi)全部死亡。 PEGASIS算法鏈?zhǔn)浇Y(jié)構(gòu)圖PEFASIS協(xié)議的優(yōu)點(diǎn)是減少了LEACH在簇重構(gòu)過程中所產(chǎn)生的開銷，并且通過數(shù)據(jù)融合降低了收發(fā)過程的次數(shù)，從而降低了能量的消耗，仿真結(jié)果表明，與LEACH協(xié)議相比，PEGASIS能夠提高網(wǎng)絡(luò)的生存周期近2倍。其次，鏈上每個(gè)節(jié)點(diǎn)向鄰居發(fā)送和接收數(shù)據(jù)。不同LEACH算法的多簇結(jié)構(gòu)，PEGASIS算法在傳感器節(jié)點(diǎn)中采用鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行連接。節(jié)點(diǎn)與匯聚節(jié)點(diǎn)間的通信過程是輪流進(jìn)行的，當(dāng)所有節(jié)點(diǎn)都與匯聚點(diǎn)通信后，節(jié)點(diǎn)間再進(jìn)行新一輪的輪流通信。（9）PowerEfficient Gathering in Sensor Information Systems（PEGASIS）[23]算法是在LEACH算法的基礎(chǔ)上改進(jìn)設(shè)計(jì)的。采用LEACH方法使因能量耗盡而失效的節(jié)點(diǎn) 呈隨機(jī)分布狀態(tài)，因而與一般靜態(tài)分簇算法相比，LEACH可以將網(wǎng)絡(luò)生命周期延長15%。T(n)可表示為：，nG 式21，其他其中：P是簇頭所在所有節(jié)點(diǎn)中所占的比率；r是選舉輪數(shù)；r mod(1/P)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)；G是這一輪循環(huán)中從未當(dāng)選過簇頭的節(jié)點(diǎn)集合。LEACH算法選舉簇頭的具體過程如下：每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)介于0到1之間的隨機(jī)數(shù)，如果這個(gè)數(shù)小于閾值T(n)，則廣播消息通知其他所有節(jié)點(diǎn)自己是簇頭節(jié)點(diǎn)，其他節(jié)點(diǎn)則根據(jù)接收到的信號(hào)的強(qiáng)弱來決定加入哪個(gè)簇。（8）LEACH算法 lowenergy adaptive clustering hierarchy（LEACH）[22]算法是無線傳感器網(wǎng)絡(luò)中最早提出的一種自適應(yīng)分簇拓?fù)渌惴?。在大多?shù)的模擬情景中，DFTM也成功地構(gòu)建了一個(gè)無死端拓?fù)浣Y(jié)構(gòu)。通過仿真進(jìn)行了一系列的數(shù)值模擬，將DFTM的性能與GAF、SPAN這些傳統(tǒng)的拓?fù)渚S護(hù)策略進(jìn)行了比較。每個(gè)活躍節(jié)點(diǎn)都與處于活躍狀態(tài)的鄰居節(jié)點(diǎn)周期性地交換消息。在局部拓?fù)渚S護(hù)操作過程中，一些活動(dòng)節(jié)點(diǎn)可能會(huì)突然因?yàn)楣?jié)點(diǎn)碰撞，能量耗盡等原因而變得不可達(dá)。同時(shí)，由初始節(jié)點(diǎn)和其ANS中的節(jié)點(diǎn)的Voronoi多邊形的垂直平分線之間所包圍這些節(jié)點(diǎn)在進(jìn)入睡眠模式。在狀態(tài)7，已被選擇的節(jié)點(diǎn)成為活躍節(jié)點(diǎn)，且被指定為新的初始節(jié)點(diǎn)。否則，轉(zhuǎn)換到狀態(tài)7。初始節(jié)點(diǎn)從狀態(tài)5可能轉(zhuǎn)換到狀態(tài)6或者狀態(tài)7。而當(dāng)初始節(jié)點(diǎn)的定時(shí)器到一定時(shí)間，則進(jìn)入狀態(tài)圖4。初始節(jié)點(diǎn)隨后發(fā)出一條消息并搜索處于沒有休眠狀態(tài)的節(jié)點(diǎn)，然后轉(zhuǎn)換到狀態(tài)3接收回復(fù)。過程開始時(shí)，隨機(jī)指定一個(gè)節(jié)點(diǎn)處于活躍狀態(tài)，這個(gè)節(jié)點(diǎn)轉(zhuǎn)換到狀態(tài)1，并被稱為初始節(jié)點(diǎn)。 DFTM算法執(zhí)行過程。然后匯聚節(jié)點(diǎn)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為初始節(jié)點(diǎn)來構(gòu)建無死端的拓?fù)浣Y(jié)構(gòu)。為了確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗的均勻分布，DFTM提出了一個(gè)全局性的拓?fù)渚S護(hù)計(jì)劃，旨在執(zhí)行一個(gè)活動(dòng)節(jié)點(diǎn)切換過程。 第一種算法從原來的拓?fù)鋱D中貪婪地刪除鏈接(Deleting Links)，而第二算法從原來的拓?fù)鋱D中貪婪地添加鏈接(Adding Links). 兩種貪婪算法示意圖，圖(a)為建立于CC鏈接原始的拓?fù)鋱D，圖(b)(d)用第一種貪婪算法刪除鏈接，圖(e)和(f)用第二種算法增加鏈接。提出的兩個(gè)算法是貪婪算法。因此，協(xié)同通信的拓?fù)浣Y(jié)構(gòu)的CC鏈接只有單跳范圍內(nèi)的連接，不是所有的鏈接都加入到了CC鏈接中。如果一個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)能夠建立起協(xié)同能量檢測，那當(dāng)所有可能的直接鏈接和CC鏈接都是相通時(shí)候，文獻(xiàn)[20]保證有每一對(duì)節(jié)點(diǎn)之間的路徑的能源消耗是最低的，這將有利于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的能量高效性。 NC分裂過程示意圖（6）Ying Zhu[20]等人引入一個(gè)新的拓?fù)淇刂茊栴}：協(xié)同通信中能量有效的拓?fù)淇刂茊栴}，提出的兩種拓?fù)淇刂扑惴▉斫f(xié)同能量檢測（Cooperative Energy Spanners），使得每條路徑的能量有效性得到了保證。直到所有的NC最后成為單獨(dú)集，NC都將逐漸分開并放置在正確的位置在樹中。NC是包括尋找拓?fù)涞膫鞲衅鞴?jié)點(diǎn)的一個(gè)子集，但它們之間的關(guān)系是未知的。該算法在每一個(gè)測量的基礎(chǔ)上，逐步揭示出度數(shù)越高的樹形拓?fù)浣Y(jié)構(gòu)。算法是完全基于測量接收到的sink節(jié)點(diǎn)的信號(hào)，從而提供了一個(gè)無源拓?fù)渫茢喾椒ā？紤]到其資源的稀缺性。該方法不依賴于內(nèi)部網(wǎng)絡(luò)節(jié)點(diǎn)的合作活動(dòng)，僅通過接收到的傳感器讀數(shù)（被動(dòng)方式），不用執(zhí)行網(wǎng)絡(luò)內(nèi)的資源密集型任務(wù)，就能夠推斷出所尋找的拓?fù)浣Y(jié)構(gòu)。而涉及到無線傳感器網(wǎng)絡(luò)，大部分文獻(xiàn)提出的拓?fù)浒l(fā)現(xiàn)方法是基于內(nèi)部網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)送的鄰居信息。仿真實(shí)驗(yàn)結(jié)果表明，能量消耗在特定的主干網(wǎng)生成算法下也能夠明顯地減少，且該拓?fù)浞桨妇哂斜然诖兀╟lusterbase ）和鏈?zhǔn)剑╟hainbased ）拓?fù)涓玫哪芰坑行?。然后，因?yàn)樗械拇仡^節(jié)點(diǎn)可以通過網(wǎng)關(guān)節(jié)點(diǎn)和門戶節(jié)點(diǎn)彼此通信，所以數(shù)據(jù)的傳輸和融合就可以沿著這個(gè)骨干網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)中的信息收集。簇頭節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)和門戶節(jié)點(diǎn)當(dāng)選為形成作為整個(gè)網(wǎng)絡(luò)的基礎(chǔ)骨干網(wǎng)絡(luò)。CKBH數(shù)據(jù)收集方法分為若干輪。不管移動(dòng)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布如何變化，可以證明，節(jié)點(diǎn)的網(wǎng)絡(luò)連通性可以保持。骨干網(wǎng)的節(jié)點(diǎn)主要分為三種類型的節(jié)點(diǎn)，稱為簇頭節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)和門戶節(jié)點(diǎn)。上層是骨干網(wǎng)，是整個(gè)網(wǎng)絡(luò)傳輸數(shù)據(jù)的基礎(chǔ)。為此，Longfei Wen[18]等人提出了“連接保持”分層拓?fù)淠Ｐ停╟onnectingkeeping），該模型是一類基于主干鏈路（backbonebased）的拓?fù)浞绞?，其主干網(wǎng)絡(luò)是基于網(wǎng)絡(luò)連接度來生成的。 子外層（external sublayer）網(wǎng)絡(luò)拓?fù)涫疽鈭D處于外層（網(wǎng)絡(luò)邊緣）的節(jié)點(diǎn)則在這種機(jī)制的調(diào)節(jié)下，在保證監(jiān)測任務(wù)正常工作的前提下，外層的節(jié)點(diǎn)交替進(jìn)入活躍狀態(tài)，控制外層節(jié)點(diǎn)的能量消耗。而處于活躍狀態(tài)節(jié)點(diǎn)的活躍時(shí)間越少，則節(jié)點(diǎn)的能量消耗越少。（3）[17]等人提出了一種較具體的網(wǎng)絡(luò)拓?fù)淇刂茩C(jī)制，這種機(jī)制在不影響網(wǎng)絡(luò)連通和覆蓋的情況下顯著減少了能量消耗。（3）更換有故障的節(jié)點(diǎn)：可達(dá)通信節(jié)點(diǎn)的集合確定后，選擇離原失效節(jié)點(diǎn)最近的節(jié)點(diǎn)來代替故障節(jié)點(diǎn)，以保證在恢復(fù)過程中所有節(jié)點(diǎn)移動(dòng)的距離最短，以及最快的恢復(fù)速度和最小開銷。如果是網(wǎng)絡(luò)連接的關(guān)鍵節(jié)點(diǎn)則執(zhí)行SRT(shortestpath routing table) 算法；（2）最小塊標(biāo)識(shí)：通過尋找每一個(gè)可以與原失效節(jié)點(diǎn)直接通信方向上可達(dá)的節(jié)點(diǎn)鄰居集合，選擇節(jié)點(diǎn)最少的節(jié)點(diǎn)集合作為標(biāo)識(shí)塊。圖a所示為A10節(jié)點(diǎn)是一個(gè)關(guān)鍵節(jié)點(diǎn)，圖b所示為A10節(jié)點(diǎn)失效后原網(wǎng)絡(luò)拓?fù)鋵嗔殉刹幌噙B的兩部分，黑色節(jié)點(diǎn)表示A10節(jié)點(diǎn)一跳范圍內(nèi)的鄰居節(jié)點(diǎn)，圖c表示通過算法確定A14為關(guān)鍵節(jié)點(diǎn)的鄰居集合為最小塊，以及A14節(jié)點(diǎn)代替失效節(jié)點(diǎn)A10的移動(dòng)位置，圖d和圖e表示A14節(jié)點(diǎn)移動(dòng)到新位置后，它的子節(jié)點(diǎn)根據(jù)最短路徑應(yīng)該移動(dòng)的位置，圖f表示節(jié)點(diǎn)恢復(fù)后新的拓?fù)鋱D。黑色節(jié)點(diǎn)參與到了恢復(fù)過程，灰色節(jié)點(diǎn)則移動(dòng)了位置。（2）Ameer A. Abbasi[16]等人提出的LeDiR算法一種基于最小變化拓?fù)浣Y(jié)構(gòu)的修復(fù)算法，該算法是一個(gè)本地化的分布式算法，充分利用網(wǎng)絡(luò)中現(xiàn)有的路由發(fā)現(xiàn)方法和沒有施加任何額外的故障前的通信開銷。后者在理論上可以得到一個(gè)近似的拓?fù)淇刂茊栴}的最佳解決方案。這兩種方法都是反復(fù)添加一組邊的拓?fù)浣Y(jié)構(gòu)來連接一個(gè)或多個(gè)的空間時(shí)間關(guān)系圖中的節(jié)點(diǎn)對(duì)?；诳臻g時(shí)間關(guān)系圖建立的稀疏結(jié)構(gòu)的拓?fù)淇刂扑惴ň褪且跁r(shí)間T內(nèi)構(gòu)造一個(gè)空間時(shí)間關(guān)系圖，并使得關(guān)系圖內(nèi)的總的路徑成本最低化，還要使各個(gè)節(jié)點(diǎn)在時(shí)間T內(nèi)至少可以通過其他節(jié)點(diǎn)中繼后能相互通信?？臻g時(shí)間關(guān)系圖容易得到空間和時(shí)間網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的維數(shù)。也就是說，假設(shè)每個(gè)時(shí)隙的有足夠長的時(shí)間來用于一個(gè)信息包的傳輸。在t=0時(shí)刻有數(shù)據(jù)包要發(fā)送，在t =2時(shí)刻將其傳遞到，在t =3時(shí)刻將其傳