《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 面向FPGA的DSR路由表項設計與實現(xiàn)方法
面向FPGA的DSR路由表項設計與實現(xiàn)方法
2018年電子技術應用第12期
李 森,,李 波,閆中江,,楊 懋
西北工業(yè)大學 電子信息學院,,陜西 西安710072
摘要: 近年來,,Ad Hoc網(wǎng)絡在無線通信領域發(fā)展迅猛。它是一種不依賴預設通信設施的新型組網(wǎng)技術,,具有很高的靈活性與獨立性,,適用于許多網(wǎng)絡設備臨時架設困難的場景。DSR協(xié)議是Ad Hoc網(wǎng)絡的一種按需路由控制協(xié)議,,也是Ad Hoc網(wǎng)絡中最有發(fā)展?jié)摿Φ穆酚蓞f(xié)議,。DSR協(xié)議的核心是用于各節(jié)點之間相互通信的路由表項管理。設計與實現(xiàn)了一種基于有限狀態(tài)機(FSM)支持DSR路由表項管理的FPGA方法,。
關鍵詞: adhoc DSR 路由表項 FPGA FSM
中圖分類號: TN929.5
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.181505
中文引用格式: 李森,,李波,閆中江,等. 面向FPGA的DSR路由表項設計與實現(xiàn)方法[J].電子技術應用,,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)絡具有無中心控制節(jié)點,、路由多跳,、拓撲動態(tài)等特點,可以用于不能預設網(wǎng)絡設施的場合和需要快速自動組網(wǎng)的場合,,例如:戰(zhàn)場,、無人煙山區(qū)、救災現(xiàn)場等[2],。因此Ad Hoc網(wǎng)絡在當今社會具有非常廣泛的應用場景,。

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

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

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

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

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

1.1 總體方案

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

tx4-t1.gif

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

    路由管理有限狀態(tài)機的設計是基于DSR協(xié)議,有限狀態(tài)機的狀態(tài)跳轉(zhuǎn)如圖2所示,。若需要查找一條路由時,,狀態(tài)機從IDLE狀態(tài)跳轉(zhuǎn)到路由查找狀態(tài)并生成路由查找使能,,當狀態(tài)機收到查找操作結束信號時,狀態(tài)機跳轉(zhuǎn)到IDLE狀態(tài),;若需要刪除路由時,,狀態(tài)機從IDLE狀態(tài)跳轉(zhuǎn)到路由刪除狀態(tài)并生成路由刪除使能,當狀態(tài)機收到刪除操作結束信號時,,狀態(tài)機跳轉(zhuǎn)到IDLE狀態(tài),;若需要存儲一條路由時,狀態(tài)機從IDLE狀態(tài)跳轉(zhuǎn)到路由緩存狀態(tài)并生成路由存儲使能給路由管理模塊,,當狀態(tài)機收到路由存儲操作結束信號時,,狀態(tài)機跳轉(zhuǎn)回IDLE狀態(tài)。

tx4-t2.gif

1.3 路由管理模塊

    路由管理模塊具體細化為4個模塊:生存周期模塊,、路由寫模塊、路由讀模塊,、路由刪除模塊,。路由管理模塊對路由表項的管理是通過對路由BD(Buffer Description)以及它的地址進行操作完成的。BD包含路由的某些信息,,例如:該路由所導向目的節(jié)點IP地址,、路由長度、路由表項存儲單元的起始地址,。根據(jù)一個BD就可以讀取一條完整路由,。

    (1)路由寫模塊存儲路由與生成該路由的BD。需要存儲一條路由時,,模塊將該路由存儲于RT表一個空條目(條目容量為16個周期數(shù)據(jù)長度),。同時生成一個新BD存入BD表。

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

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

    (4)路由刪除模塊維護一個有效BD地址的單向鏈表,。路由存儲時,將包含新BD地址的表項插入鏈表,;路由查找時,,查找一個有效BD地址;路由過期時,,從鏈表中刪除該條路由的有效BD地址表項,;路由刪除時,刪除包含斷開鏈路的路由有效BD地址的表項,。

    路由存儲時,,將路由存于RT表一個空條目,。同時生成一個對該條目進行描述的BD并存于BD表中;它的地址被插入鏈表中,,并為它設定生存周期,。

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

tx4-t3.gif

2 實驗仿真與分析

2.1 總體功能仿真

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

tx4-t4.gif

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

tx4-t5.gif

tx4-t6.gif

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

tx4-t7.gif

tx4-t8.gif

2.2 總體性能仿真與分析

    表1是一條路由存儲的時延隨周期變化的情況。由表1可知,,隨著存儲的路由周期變長,,模塊路由存儲的時延均在166.4 ns左右。

tx4-b1.gif

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

tx4-b2+b3.gif

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

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

tx4-b4+b5.gif

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

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

tx4-b6.gif

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

3 結論

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

參考文獻

[1] 王海濤.Ad Hoc網(wǎng)絡[J].電信技術,,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] 屠梓浩,,吳榮泉,錢立群.無線Ad Hoc網(wǎng)絡DSR路由協(xié)議的優(yōu)化設計[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)機的建模與優(yōu)化設計[J].重慶理工大學學報(自然科學),,2007,21(5):55-58.

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



作者信息:

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

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

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