《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 面向FPGA的DSR路由表項(xiàng)設(shè)計(jì)與實(shí)現(xiàn)方法
面向FPGA的DSR路由表項(xiàng)設(shè)計(jì)與實(shí)現(xiàn)方法
2018年電子技術(shù)應(yīng)用第12期
李 森,，李 波，閆中江，楊 懋
西北工業(yè)大學(xué) 電子信息學(xué)院,，陜西 西安710072
摘要： 近年來(lái)，Ad Hoc網(wǎng)絡(luò)在無(wú)線通信領(lǐng)域發(fā)展迅猛,。它是一種不依賴預(yù)設(shè)通信設(shè)施的新型組網(wǎng)技術(shù),，具有很高的靈活性與獨(dú)立性，適用于許多網(wǎng)絡(luò)設(shè)備臨時(shí)架設(shè)困難的場(chǎng)景,。DSR協(xié)議是Ad Hoc網(wǎng)絡(luò)的一種按需路由控制協(xié)議,，也是Ad Hoc網(wǎng)絡(luò)中最有發(fā)展?jié)摿Φ穆酚蓞f(xié)議。DSR協(xié)議的核心是用于各節(jié)點(diǎn)之間相互通信的路由表項(xiàng)管理,。設(shè)計(jì)與實(shí)現(xiàn)了一種基于有限狀態(tài)機(jī)（FSM）支持DSR路由表項(xiàng)管理的FPGA方法,。
關(guān)鍵詞： adhoc DSR 路由表項(xiàng) FPGA FSM
中圖分類號(hào)： TN929.5
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.181505
中文引用格式： 李森，李波,，閆中江,，等. 面向FPGA的DSR路由表項(xiàng)設(shè)計(jì)與實(shí)現(xiàn)方法[J].電子技術(shù)應(yīng)用，2018,，44(12)：89-92.
英文引用格式： Li Sen,，Li Bo，Yan Zhongjiang,，et al. Design and implementation of DSR routing table entries for FPGA[J]. Application of Electronic Technique,，2018，44(12)：89-92.
Design and implementation of DSR routing table entries for FPGA
Li Sen，Li Bo,，Yan Zhongjiang,，Yang Mao
School of Electronics and Information，Northwestern Polytechnical University,，Xi′an 710072,，China
Abstract： Ad Hoc network is a new type of communication technology that has developed rapidly in the field of wireless communication in recent years. It does not rely on fixed communications infrastructure, and has great flexibility and independence. It is applicable to many scenarios where network cabling is difficult. DSR protocol is an on-demand routing control protocol designed for Ad Hoc networks. It is considered to be one of the most promising Ad Hoc network routing protocols. The core of the DSR protocol is the routing table entry that the node manages to communicate with other nodes. This article focuses on designing and implementing an FPGA method that supports DSR routing table entry management based on finite state machines (FSM).
Key words : Ad Hoc；DSR,；routing table entry,；FPGA；FSM

0 引言

    Ad Hoc[1]網(wǎng)絡(luò)具有無(wú)中心控制節(jié)點(diǎn),、路由多跳,、拓?fù)鋭?dòng)態(tài)等特點(diǎn)，可以用于不能預(yù)設(shè)網(wǎng)絡(luò)設(shè)施的場(chǎng)合和需要快速自動(dòng)組網(wǎng)的場(chǎng)合,，例如：戰(zhàn)場(chǎng),、無(wú)人煙山區(qū)、救災(zāi)現(xiàn)場(chǎng)等[2],。因此Ad Hoc網(wǎng)絡(luò)在當(dāng)今社會(huì)具有非常廣泛的應(yīng)用場(chǎng)景,。

    動(dòng)態(tài)源路由協(xié)議(Dynamic Source Routing)[3]是一種按需路由協(xié)議，是十分適用于Ad Hoc網(wǎng)絡(luò)的路由協(xié)議,。在DSR協(xié)議中,，路由表的表項(xiàng)都是按需建立的。路由過(guò)期或鏈路斷開(kāi),，表項(xiàng)就失去作用了,。為減少路由不斷建立而產(chǎn)生的網(wǎng)絡(luò)開(kāi)銷，按需建立的路由都由源節(jié)點(diǎn)存儲(chǔ),，用于與目的節(jié)點(diǎn)通信[4]。因此DSR協(xié)議的核心是管理各節(jié)點(diǎn)之間通信的路由表項(xiàng),。

    目前,，國(guó)內(nèi)外針對(duì)Ad Hoc網(wǎng)絡(luò)的研究大多是基于軟件的，使用的軟件平臺(tái)有NS2,、GloMoSim,、OPNET等。因此,，DSR協(xié)議的核心功能——路由表項(xiàng)管理,，也是基于軟件完成的。目前為止,，還未有基于FPGA實(shí)現(xiàn)DSR路由表項(xiàng)管理的先例,。

    使用硬件實(shí)現(xiàn) DSR協(xié)議功能將減少功耗和延遲時(shí)間，延長(zhǎng)移動(dòng)設(shè)備的電池使用時(shí)間[5],。Ad Hoc網(wǎng)絡(luò)中,，通過(guò)硬件與嵌入式芯片聯(lián)系在一起,，使得操作速度的增加與功耗降低，處理時(shí)間還可以用于其他操作[6],。此外,，使用硬件實(shí)現(xiàn)DSR協(xié)議可以更快地建立呼叫和更改動(dòng)態(tài)拓?fù)?sup>[7]。因此,，使用FPGA實(shí)現(xiàn)DSR路由表項(xiàng)管理具有很好的實(shí)際用途,。

    本文為在FPGA中支持DSR協(xié)議的路由表項(xiàng)管理功能，設(shè)計(jì)一種基于有限狀態(tài)機(jī)[8]的實(shí)現(xiàn)方法,。本文的設(shè)計(jì)中,，狀態(tài)機(jī)包含一個(gè)初始狀態(tài)和3個(gè)功能狀態(tài)。有限狀態(tài)機(jī)的3個(gè)功能狀態(tài)一起聯(lián)合實(shí)現(xiàn)路由存儲(chǔ),、路由查找,、路由刪除的功能。有限狀態(tài)機(jī)使得硬件代碼符合時(shí)序電路的風(fēng)格,。此外,，綜合后的代碼在電路物理實(shí)現(xiàn)時(shí)使得時(shí)延特性與功耗更加優(yōu)化[9]。

1 DSR路由表項(xiàng)管理的實(shí)現(xiàn)

1.1 總體方案

    總體方案如圖1所示,，設(shè)計(jì)分為兩個(gè)部分：路由管理有限狀態(tài)機(jī)模塊以及路由管理模塊,。有限狀態(tài)機(jī)根據(jù)需求跳轉(zhuǎn)到不同的功能狀態(tài)，生成不同的操作使能,，用以驅(qū)動(dòng)路由管理模塊對(duì)路由表項(xiàng)進(jìn)行添加,、查找、刪除,。路由管理模塊完成對(duì)路由表項(xiàng)的操作后,，有限狀態(tài)機(jī)從現(xiàn)有狀態(tài)跳轉(zhuǎn)回初態(tài)。

tx4-t1.gif

1.2 路由管理有限狀態(tài)機(jī)

    路由管理有限狀態(tài)機(jī)的設(shè)計(jì)是基于DSR協(xié)議,，有限狀態(tài)機(jī)的狀態(tài)跳轉(zhuǎn)如圖2所示,。若需要查找一條路由時(shí)，狀態(tài)機(jī)從IDLE狀態(tài)跳轉(zhuǎn)到路由查找狀態(tài)并生成路由查找使能,，當(dāng)狀態(tài)機(jī)收到查找操作結(jié)束信號(hào)時(shí),，狀態(tài)機(jī)跳轉(zhuǎn)到IDLE狀態(tài)；若需要?jiǎng)h除路由時(shí),，狀態(tài)機(jī)從IDLE狀態(tài)跳轉(zhuǎn)到路由刪除狀態(tài)并生成路由刪除使能,，當(dāng)狀態(tài)機(jī)收到刪除操作結(jié)束信號(hào)時(shí)，狀態(tài)機(jī)跳轉(zhuǎn)到IDLE狀態(tài),；若需要存儲(chǔ)一條路由時(shí),，狀態(tài)機(jī)從IDLE狀態(tài)跳轉(zhuǎn)到路由緩存狀態(tài)并生成路由存儲(chǔ)使能給路由管理模塊，當(dāng)狀態(tài)機(jī)收到路由存儲(chǔ)操作結(jié)束信號(hào)時(shí)，狀態(tài)機(jī)跳轉(zhuǎn)回IDLE狀態(tài),。

tx4-t2.gif

1.3 路由管理模塊

    路由管理模塊具體細(xì)化為4個(gè)模塊：生存周期模塊,、路由寫(xiě)模塊、路由讀模塊,、路由刪除模塊,。路由管理模塊對(duì)路由表項(xiàng)的管理是通過(guò)對(duì)路由BD(Buffer Description)以及它的地址進(jìn)行操作完成的。BD包含路由的某些信息,，例如：該路由所導(dǎo)向目的節(jié)點(diǎn)IP地址,、路由長(zhǎng)度、路由表項(xiàng)存儲(chǔ)單元的起始地址,。根據(jù)一個(gè)BD就可以讀取一條完整路由,。

    (1)路由寫(xiě)模塊存儲(chǔ)路由與生成該路由的BD。需要存儲(chǔ)一條路由時(shí),，模塊將該路由存儲(chǔ)于RT表一個(gè)空條目（條目容量為16個(gè)周期數(shù)據(jù)長(zhǎng)度）,。同時(shí)生成一個(gè)新BD存入BD表。

    (2)路由讀模塊完成兩個(gè)功能：①讀取一條有效路由,；②查收所有包含斷開(kāi)鏈路的有效路由并反饋給路由刪除模塊,。

    (3)生存周期模塊包含256個(gè)計(jì)數(shù)器(網(wǎng)絡(luò)只支持256個(gè)節(jié)點(diǎn))，為每個(gè)新BD設(shè)置生存周期,。

    (4)路由刪除模塊維護(hù)一個(gè)有效BD地址的單向鏈表,。路由存儲(chǔ)時(shí)，將包含新BD地址的表項(xiàng)插入鏈表,；路由查找時(shí),，查找一個(gè)有效BD地址；路由過(guò)期時(shí),，從鏈表中刪除該條路由的有效BD地址表項(xiàng),；路由刪除時(shí)，刪除包含斷開(kāi)鏈路的路由有效BD地址的表項(xiàng),。

    路由存儲(chǔ)時(shí),，將路由存于RT表一個(gè)空條目。同時(shí)生成一個(gè)對(duì)該條目進(jìn)行描述的BD并存于BD表中,；它的地址被插入鏈表中，并為它設(shè)定生存周期,。

    路由管理原理如圖3所示,。查找路由時(shí)，首先讀取鏈表尾條目,，根據(jù)有效BD地址讀取BD表一個(gè)有效BD,，比對(duì)目的節(jié)點(diǎn)地址。若匹配，根據(jù)RT長(zhǎng)度與有效RT地址讀取RT表一條完整的路由,。若不匹配,，則根據(jù)鏈表指針讀取鏈表的前一個(gè)條目，然后重復(fù)上面所述的操作,，直到目標(biāo)路由或者查完鏈表,。路由過(guò)期即路由的BD過(guò)期，將包含該BD地址的條目從鏈表中刪除,。路由刪除時(shí),，需要重復(fù)路由查找過(guò)程，讀取全部有效路由,，并逐條比對(duì)是否包含斷開(kāi)鏈路,。將包含斷開(kāi)鏈路的BD地址條目從鏈表中剔除。刪除操作完成后,，更新后一個(gè)條目的鏈表指針，使得鏈表完整,。

tx4-t3.gif

2 實(shí)驗(yàn)仿真與分析

2.1 總體功能仿真

    圖4是路由存儲(chǔ)仿真結(jié)果,。標(biāo)號(hào)①是存儲(chǔ)的路由信息，store_route_en是路由存儲(chǔ)的使能,，hop[31:0]路由數(shù)據(jù)周期數(shù),，did[31:0]目的節(jié)點(diǎn)地址，data_route[31:0]是路由數(shù)據(jù),。

tx4-t4.gif

    圖5,、圖6是路由查找仿真結(jié)果。did_to_rd_rt[31:0]是目的節(jié)點(diǎn)地址,。標(biāo)號(hào)③與標(biāo)號(hào)④分別是存儲(chǔ)與讀取的路由數(shù)據(jù),，兩者是一樣的，故路由查找結(jié)果正確,。

tx4-t5.gif

tx4-t6.gif

    圖7與圖8是路由刪除仿真結(jié)果,。標(biāo)號(hào)①是存儲(chǔ)的路由，標(biāo)號(hào)③是需要?jiǎng)h除路由包含的前端節(jié)點(diǎn)ID1與后端節(jié)點(diǎn)ID2地址,。標(biāo)號(hào)②是路由存儲(chǔ)時(shí)插入鏈表的有效BD地址,，標(biāo)號(hào)④是路由刪除后鏈表釋放的BD地址。兩者的數(shù)據(jù)一致,，路由刪除結(jié)果正確,。

tx4-t7.gif

tx4-t8.gif

2.2 總體性能仿真與分析

    表1是一條路由存儲(chǔ)的時(shí)延隨周期變化的情況。由表1可知,，隨著存儲(chǔ)的路由周期變長(zhǎng),，模塊路由存儲(chǔ)的時(shí)延均在166.4 ns左右,。

tx4-b1.gif

    若路由不過(guò)期，每條路由固定長(zhǎng)度且每次查找第一條存儲(chǔ)路由,，表2是長(zhǎng)度為2周期的路由查找時(shí)延隨著條數(shù)變化情況,。表3是長(zhǎng)度為8周期的路由查找時(shí)延隨著條數(shù)變化情況。

tx4-b2+b3.gif

    由表2,、表3可知,，路由周期固定,，隨著存儲(chǔ)條數(shù)增加查找路由的時(shí)延快速增加,。在路由表中存儲(chǔ)路由條數(shù)固定情況下，路由查找時(shí)延隨著路由長(zhǎng)度的增加緩慢增加,。路由查找的時(shí)延在ns級(jí),，說(shuō)明查找速度很快。

    表4是長(zhǎng)度為2周期的路由刪除時(shí)延隨著條數(shù)變化情況,。表5是長(zhǎng)度為8周期的路由刪除時(shí)延隨著條數(shù)變化情況。

tx4-b4+b5.gif

    由表4,、表5可知，在存儲(chǔ)周期固定的路由情況下,，隨著存儲(chǔ)條數(shù)增加,，刪除路由的時(shí)延快速增加,，幾乎是2倍的速率,。在路由表中存儲(chǔ)路由條數(shù)固定情況下，路由刪除時(shí)延隨著路由長(zhǎng)度的增加緩慢增加,。 但路由刪除的時(shí)延還在μs級(jí)以下,，說(shuō)明刪除速度依然很快,。從路由存儲(chǔ),、查找、刪除的結(jié)果分析上來(lái)說(shuō),，路由管理模塊工作效率是非常高的,。

    模塊設(shè)計(jì)使用vivado2015.2平臺(tái)，開(kāi)發(fā)板采用Xilinx的VC707,，使用的設(shè)備是XC7VX485T,。片上總功耗為28.379 W，模塊功耗為11.755 W,。片上各部分資源使用情況如表6所示,。

tx4-b6.gif

    由表6可見(jiàn)，使用硬件實(shí)現(xiàn)DSR路由表項(xiàng)管理所占用的硬件資源非常少,，功耗十分小,。

3 結(jié)論

    本文針對(duì)在FPGA中支持DSR路由協(xié)議的核心內(nèi)容路由表項(xiàng)管理提出了一種基于有限狀態(tài)機(jī)的設(shè)計(jì)與實(shí)現(xiàn)方法。建立實(shí)現(xiàn)模型,，使用vivado2015.2平臺(tái)進(jìn)行仿真,，仿真結(jié)果很好地驗(yàn)證了預(yù)期目標(biāo)。通過(guò)實(shí)驗(yàn)分析,，發(fā)現(xiàn)使用FPGA實(shí)現(xiàn)DSR路由表項(xiàng)管理時(shí)延非常低,，資源占用十分少，功耗很小,。

參考文獻(xiàn)

[1] 王海濤.Ad Hoc網(wǎng)絡(luò)[J].電信技術(shù),，2005(8)：97-99.

[2] CONTI M，GIORDANO S.Mobile ad hoc networking: milestones, challenges, and new research directions[J].Communications Magazine IEEE,，2014,，52(1)：85-96.

[3] JOHNSON D B,，MALTZ D A.Dynamic source routing in ad hoc wireless networks[C].Mobile Computing,，2016：153-181.

[4] 屠梓浩，吳榮泉,，錢立群.無(wú)線Ad Hoc網(wǎng)絡(luò)DSR路由協(xié)議的優(yōu)化設(shè)計(jì)[J].計(jì)算機(jī)工程,，2009，35(4)：97-99.

[5] RAMAKRISHNAN M,，SHANMUGAVEL S.FPGA implementation of AODV routing protocol in MANET[C].International Conference on Industrial and Information Systems.IEEE,，2006：470-473.

[6] RATHINAM A，NATARAJAN V,，VANILA S,，et al.An FPGA implementation of improved AODV routing protocol for route repair scheme[M].IEEE Computer Society，2008：971-974.

[7] RAMAKRISHNAN M,，SHANMUGAVEL S.FPGA implementation of DSDV based router in mobile adhoc network[C].India Conference.IEEE,，2006：1-5.

[8] 陳勇.有限狀態(tài)機(jī)的建模與優(yōu)化設(shè)計(jì)[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2007,，21(5)：55-58.

[9] 彼德·明斯,，伊恩·艾利奧特，明斯,，等.基于FSM和VerilogHDL的數(shù)字電路設(shè)計(jì)[M].北京：機(jī)械工業(yè)出版社,，2016.



作者信息:

李  森，李  波,，閆中江,，楊  懋

(西北工業(yè)大學(xué) 電子信息學(xué)院,，陜西 西安710072）

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載,。