基于柏拉圖立體的無線三維片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)及路由

張鳴皓　趙成龍

摘要：由于片上微型天線的成功研制，片上系統(tǒng)（SoC）內(nèi)部的無線通信得到了實現(xiàn)。為無線片上網(wǎng)絡(luò)的思想提供了基礎(chǔ)的支持，已有研究證明無線片上網(wǎng)絡(luò)概念正是應(yīng)對有線片上網(wǎng)絡(luò)局限性而提出的新的解決方案。文章對基于柏拉圖立體模型為拓撲結(jié)構(gòu)的無線片上網(wǎng)絡(luò)中的功耗和延遲能性能并與傳統(tǒng)的有線片上拓撲結(jié)構(gòu)進行了比較。

關(guān)鍵詞：無線片上網(wǎng)絡(luò)；拓撲結(jié)構(gòu)；柏拉圖立體；功耗；延遲 文獻標識碼：A

中圖分類號：TP391 文章編號：1009-2374（2016）34-0020-02 DOI：10.13535/j.cnki.11-4406/n.2016.34.010

隨著技術(shù)的進步、集成電路工藝的發(fā)展，早期片上系統(tǒng)（SoC）由于使用共享和專用總線的特性而使得片上互連結(jié)構(gòu)面臨擴展性差和延遲高等性能問題。基于無線片上網(wǎng)路的高帶寬無線長距離單跳鏈接代替多跳有線鏈接可以顯著地減少延遲，加快芯片內(nèi)部的通信速度。同時無線片上網(wǎng)絡(luò)對于片上系統(tǒng)的擴展性和適用性明顯優(yōu)于有線的片上網(wǎng)絡(luò)，那么如何正確地構(gòu)建合理的無線片上網(wǎng)路的拓撲結(jié)構(gòu)就顯得尤為重要了。

1 無線片上網(wǎng)絡(luò)

本文提出了一種基于柏拉圖立體思想的六面體架構(gòu)。在這個基于柏拉圖立體的正六面體結(jié)構(gòu)中，將無線節(jié)點安放在正六面體的頂點上。在基于無線的3D-mesh結(jié)構(gòu)中，正六面體的八個節(jié)點之間的連線就構(gòu)成了一個簡單的柏拉圖立體。至此，基于柏拉圖立體的三維無線片上網(wǎng)絡(luò)中，存在無線節(jié)點的層間消息傳送就可以依靠無線路由器進行快速的數(shù)據(jù)包傳輸。本文同時提出了使用于此正六面體無線片上網(wǎng)絡(luò)架構(gòu)的路由算法。

2 拓撲及路由算法

2.1 柏拉圖立體

本文中我們使用的是最基礎(chǔ)的正六面體結(jié)構(gòu)。本文所研究的是一個8×8的4層一共256個IP Cores的同構(gòu)片上網(wǎng)絡(luò)架構(gòu)，這樣通過多層架構(gòu)很適合研究柏拉圖立體在無線片上網(wǎng)絡(luò)上的應(yīng)用。為了實現(xiàn)這樣設(shè)計的架構(gòu)，采用了目前比較流行的同構(gòu)片上網(wǎng)絡(luò)仿真器AccessNoxim_v2.0。改進為在該拓撲結(jié)構(gòu)中選取第一和第四層在這兩層之間建立無線連接，同時這兩層中分別建立四個無線路由節(jié)點。正六面體的柏拉圖立體即為立方體，修改后的拓撲結(jié)構(gòu)中的每個無線路由節(jié)點即為正六面體中的各個頂點。將第一層和第四層8×8的Mesh結(jié)構(gòu)分別分為四個子網(wǎng)，每個子網(wǎng)為4×4的結(jié)構(gòu)并且每個子網(wǎng)中分配一個無線路由節(jié)點如圖1所示。在Noxim仿真器中現(xiàn)有的拓撲結(jié)構(gòu)基礎(chǔ)上增加無線路由節(jié)點和無線連接構(gòu)成柏拉圖立體中的正六面體，使其可以應(yīng)用到混合無線片上網(wǎng)絡(luò)中。

定義節(jié)點坐標為N（x，y，z）。其中第一層的節(jié)點（2，2，0）、（5，2，0）、（2，5，0）、（5，5，0）和第四層的（2，2，3）、（5，2，3）、（2，5，3）、（5，5，3）八個節(jié)點為無線節(jié)點，分別記為：WR0-WR7。中間兩層不存在無線節(jié)點。

2.2 路由算法

基于本文提出的柏拉圖立體架構(gòu)，傳統(tǒng)的XYZ路由算法顯然不適合該架構(gòu)下的節(jié)點之間的信息傳遞，因此提出了一種基于XYZ路由算法的適用于無線片上網(wǎng)絡(luò)架構(gòu)的新型算法。無線節(jié)點之間是可以兩兩任意通信的，在提出的路由算法中，運用柏拉圖立體模型的對稱性，規(guī)定無線節(jié)點之間只能在垂直方向通信，具體描述如下：

2.2.1 判斷初始節(jié)點和目的節(jié)點是否在同一子網(wǎng)中。如果在同一子網(wǎng)中，則用基礎(chǔ)的XY路由算法實現(xiàn)初始節(jié)點到目的節(jié)點的傳輸。若不在，執(zhí)行下一步。

2.2.2 如果不在同一子網(wǎng)中，判斷源節(jié)點與目的節(jié)點之間的層數(shù)差是否大于1，即通過源節(jié)點和目的節(jié)點的Z坐標之差得到。若層數(shù)之差大于1執(zhí)行下一步，若層數(shù)之差等于1，則實行標準的XYZ路由算法進行節(jié)點之間的通信。

2.2.3 對于源節(jié)點和目的節(jié)點之差大于1的情況，則源節(jié)點的信息先傳輸?shù)綗o線節(jié)點中，通過無線節(jié)點進行傳輸。

節(jié)點之間的信息傳輸方式大致分為三種方式，下文一一舉例來說明。對于同一層的情況（實例1），如圖3所示，假設(shè)源節(jié)點坐標為A（1，1，0），目的節(jié)點坐標是B（2，0，3），那么信息傳輸?shù)穆窂骄蜑锳（1，1，0）→WR0→WR4→B（2，0，3）。其中從節(jié)點（2，2，0）（WR0）到（2，2，3）（WR4）是無線傳輸，可以看出因為無線傳輸?shù)拇嬖冢瑥脑垂?jié)點到目的節(jié)點節(jié)省了從第一層慢慢通過一個一個節(jié)點傳輸?shù)降谒膶舆@個步驟，當片上系統(tǒng)規(guī)模較大的時候，會取得巨大的延遲改進。對于相鄰兩層之間的傳輸我們統(tǒng)一使用標準的XYZ路由算法。對于最后一種中間相隔一層的情況（實例2），如圖4所示，從源節(jié)點M（1，1，1）要發(fā)送信息到N（2，0，3），此時應(yīng)用論文中提出的算法，首先不在同一層，將計算|Mz-Nz|=2，此時Z軸的坐標差是大于2的，所以此時應(yīng)該將源節(jié)點A的數(shù)據(jù)包首先傳輸?shù)骄嚯xA較近的擁有無線節(jié)點的第一層，然后再通過第一層的無線路由節(jié)點將數(shù)據(jù)信息傳輸?shù)侥康墓?jié)點。傳輸路徑如下：M→WR0→WR2→WR6→WR4→N。

3 仿真實驗

仿真實驗是在AccessNoxim_v2.0仿真器上實現(xiàn)的，該仿真器的默認架構(gòu)是同構(gòu)的3D-mesh架構(gòu)，運行于Ubuntu13操作系統(tǒng)下，操作簡單易于實現(xiàn)。通過基于AccessNoxim2.0原先的四層Mesh的三維結(jié)構(gòu)，我們將其改成基于柏拉圖立體的混合無線的三維片上網(wǎng)絡(luò)結(jié)構(gòu)。最后通過仿真實驗證明了本文提出的新型的無線片上網(wǎng)絡(luò)拓撲架構(gòu)在功耗和延遲方面與傳統(tǒng)的3D-mesh片上網(wǎng)絡(luò)架構(gòu)有了顯著的性能改善。

3.1 平均時延

片上網(wǎng)絡(luò)中產(chǎn)生的延遲（D）主要是來自于輸入和輸出延遲，即從數(shù)據(jù)流輸入信道進入到從輸出信道輸出所用的時間。為了計算片上網(wǎng)絡(luò)中的延遲，用下面的延遲模型計算。

D=Di+Do （1）

AD=D/SP （2）

式（1）中：D為總延遲值；Di為輸入端延遲；Do為輸出端延遲，總的延遲等于輸入信道產(chǎn)生的延遲和輸出信道產(chǎn)生的延遲的和。式（2）中：AD為平均延遲；SP為數(shù)據(jù)包大小，平均延遲的值等于平均每個數(shù)據(jù)包傳輸產(chǎn)生的延遲，即總延遲值除以數(shù)據(jù)包總量。

有關(guān)平均時延的仿真實驗的結(jié)果表明，在注入率較低的情況下，性能并沒有顯著的提升。但當注入率逐漸增大，有線片上網(wǎng)絡(luò)的時延和無線片上網(wǎng)絡(luò)的時延差距越來越明顯。

通過仿真數(shù)據(jù)可以看出，混合無線片網(wǎng)的延遲在較低數(shù)據(jù)流注入率的情況下差別不大，當注入率大于0.03后，改進后的仿真器在延遲方面的性能表現(xiàn)明顯優(yōu)于之前的有線拓撲結(jié)構(gòu)。

3.2 總功耗

仿真器運行的功耗主要來自于處理機產(chǎn)生的功耗和片上網(wǎng)路中數(shù)據(jù)通信產(chǎn)生的功耗。

P=Pn+Ppe （3）

式（3）中：P為總功耗值；Pn為片上網(wǎng)絡(luò)中數(shù)據(jù)通信產(chǎn)生的耗能值；Ppe為處理器產(chǎn)生的耗能值。

實驗表明，基于無線的拓撲結(jié)構(gòu)在功耗性能上也要優(yōu)于有線片網(wǎng)，注入率大于0.13后功耗趨于平穩(wěn)。

4 結(jié)論與展望

本文主要研究柏拉圖立體結(jié)構(gòu)在無線片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的應(yīng)用及其性能分析。我們深入研究并改進了意大利Catania大學(xué)基于SystemC的三維片上網(wǎng)絡(luò)仿真器AccessNoxim中關(guān)于片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)的相關(guān)部分，將原有的用于有線三維片上網(wǎng)絡(luò)的拓撲結(jié)構(gòu)改進為可用于無線片上網(wǎng)絡(luò)的混合無線片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)，該拓撲結(jié)構(gòu)可應(yīng)用于正六面體柏拉圖立體結(jié)構(gòu)。然后在仿真器中利用該混合無線片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)映射系統(tǒng)任務(wù)并分別得出其延遲等性能參數(shù)并分析其與之前混合無線片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)的差異。

本文提出了一種基于柏拉圖立體的無線片上網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，通過仿真實驗可以發(fā)現(xiàn)，這種架構(gòu)在功耗和時延上都取得了很大的改善。目前只做了一種柏拉圖立體模型，在后續(xù)的工作中將對其他幾種柏拉圖立體模型在片上網(wǎng)中的應(yīng)用做進一步的研究。本次提出的無線拓撲結(jié)構(gòu)是基于規(guī)則的3D-mesh結(jié)構(gòu)，對于不規(guī)則的片上網(wǎng)絡(luò)還沒有更好的解決辦法，這都是下一步需要研究的

方向。

作者簡介：張鳴皓（1993-），男，山西太原人，中國礦業(yè)大學(xué)（北京）機電與信息工程學(xué)院本科學(xué)生，研究方向：三維片上網(wǎng)絡(luò)；趙成龍（1994-），男，山西人，中國礦業(yè)大學(xué)（北京）機電與信息工程學(xué)院本科學(xué)生，研究方向：三維片上網(wǎng)絡(luò)。

（責(zé)任編輯：黃銀芳）