文獻(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.
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),。
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),。
1.3 路由管理模塊
路由管理模塊具體細(xì)化為4個(gè)模塊:生存周期模塊,、路由寫模塊、路由讀模塊,、路由刪除模塊,。路由管理模塊對(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)路由寫模塊存儲(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è)條目的鏈表指針,使得鏈表完整,。
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ù),。
圖5,、圖6是路由查找仿真結(jié)果。did_to_rd_rt[31:0]是目的節(jié)點(diǎn)地址,。標(biāo)號(hào)③與標(biāo)號(hào)④分別是存儲(chǔ)與讀取的路由數(shù)據(jù),,兩者是一樣的,故路由查找結(jié)果正確,。
圖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é)果正確。
2.2 總體性能仿真與分析
表1是一條路由存儲(chǔ)的時(shí)延隨周期變化的情況,。由表1可知,,隨著存儲(chǔ)的路由周期變長(zhǎng),模塊路由存儲(chǔ)的時(shí)延均在166.4 ns左右,。
若路由不過(guò)期,,每條路由固定長(zhǎng)度且每次查找第一條存儲(chǔ)路由,表2是長(zhǎng)度為2周期的路由查找時(shí)延隨著條數(shù)變化情況,。表3是長(zhǎng)度為8周期的路由查找時(shí)延隨著條數(shù)變化情況,。
由表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ù)變化情況,。
由表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所示,。
由表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)