文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.181505
中文引用格式： 李森，李波，閆中江，等. 面向FPGA的DSR路由表項設計與實現方法[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.
0 引言
Ad Hoc[1]網絡具有無中心控制節點、路由多跳、拓撲動態等特點，可以用于不能預設網絡設施的場合和需要快速自動組網的場合，例如：戰場、無人煙山區、救災現場等[2]。因此Ad Hoc網絡在當今社會具有非常廣泛的應用場景。
動態源路由協議(Dynamic Source Routing)[3]是一種按需路由協議，是十分適用于Ad Hoc網絡的路由協議。在DSR協議中，路由表的表項都是按需建立的。路由過期或鏈路斷開，表項就失去作用了。為減少路由不斷建立而產生的網絡開銷，按需建立的路由都由源節點存儲，用于與目的節點通信[4]。因此DSR協議的核心是管理各節點之間通信的路由表項。
目前，國內外針對Ad Hoc網絡的研究大多是基于軟件的，使用的軟件平臺有NS2、GloMoSim、OPNET等。因此，DSR協議的核心功能——路由表項管理，也是基于軟件完成的。目前為止，還未有基于FPGA實現DSR路由表項管理的先例。
使用硬件實現 DSR協議功能將減少功耗和延遲時間，延長移動設備的電池使用時間[5]。Ad Hoc網絡中，通過硬件與嵌入式芯片聯系在一起，使得操作速度的增加與功耗降低，處理時間還可以用于其他操作[6]。此外，使用硬件實現DSR協議可以更快地建立呼叫和更改動態拓撲[7]。因此，使用FPGA實現DSR路由表項管理具有很好的實際用途。
本文為在FPGA中支持DSR協議的路由表項管理功能，設計一種基于有限狀態機[8]的實現方法。本文的設計中，狀態機包含一個初始狀態和3個功能狀態。有限狀態機的3個功能狀態一起聯合實現路由存儲、路由查找、路由刪除的功能。有限狀態機使得硬件代碼符合時序電路的風格。此外，綜合后的代碼在電路物理實現時使得時延特性與功耗更加優化[9]。
1 DSR路由表項管理的實現
1.1 總體方案
總體方案如圖1所示，設計分為兩個部分：路由管理有限狀態機模塊以及路由管理模塊。有限狀態機根據需求跳轉到不同的功能狀態，生成不同的操作使能，用以驅動路由管理模塊對路由表項進行添加、查找、刪除。路由管理模塊完成對路由表項的操作后，有限狀態機從現有狀態跳轉回初態。
1.2 路由管理有限狀態機
路由管理有限狀態機的設計是基于DSR協議，有限狀態機的狀態跳轉如圖2所示。若需要查找一條路由時，狀態機從IDLE狀態跳轉到路由查找狀態并生成路由查找使能，當狀態機收到查找操作結束信號時，狀態機跳轉到IDLE狀態；若需要刪除路由時，狀態機從IDLE狀態跳轉到路由刪除狀態并生成路由刪除使能，當狀態機收到刪除操作結束信號時，狀態機跳轉到IDLE狀態；若需要存儲一條路由時，狀態機從IDLE狀態跳轉到路由緩存狀態并生成路由存儲使能給路由管理模塊，當狀態機收到路由存儲操作結束信號時，狀態機跳轉回IDLE狀態。
1.3 路由管理模塊
路由管理模塊具體細化為4個模塊：生存周期模塊、路由寫模塊、路由讀模塊、路由刪除模塊。路由管理模塊對路由表項的管理是通過對路由BD(Buffer Description)以及它的地址進行操作完成的。BD包含路由的某些信息，例如：該路由所導向目的節點IP地址、路由長度、路由表項存儲單元的起始地址。根據一個BD就可以讀取一條完整路由。
(1)路由寫模塊存儲路由與生成該路由的BD。需要存儲一條路由時，模塊將該路由存儲于RT表一個空條目（條目容量為16個周期數據長度）。同時生成一個新BD存入BD表。
(2)路由讀模塊完成兩個功能：①讀取一條有效路由；②查收所有包含斷開鏈路的有效路由并反饋給路由刪除模塊。
(3)生存周期模塊包含256個計數器(網絡只支持256個節點)，為每個新BD設置生存周期。
(4)路由刪除模塊維護一個有效BD地址的單向鏈表。路由存儲時，將包含新BD地址的表項插入鏈表；路由查找時，查找一個有效BD地址；路由過期時，從鏈表中刪除該條路由的有效BD地址表項；路由刪除時，刪除包含斷開鏈路的路由有效BD地址的表項。
路由存儲時，將路由存于RT表一個空條目。同時生成一個對該條目進行描述的BD并存于BD表中；它的地址被插入鏈表中，并為它設定生存周期。
路由管理原理如圖3所示。查找路由時，首先讀取鏈表尾條目，根據有效BD地址讀取BD表一個有效BD，比對目的節點地址。若匹配，根據RT長度與有效RT地址讀取RT表一條完整的路由。若不匹配，則根據鏈表指針讀取鏈表的前一個條目，然后重復上面所述的操作，直到目標路由或者查完鏈表。路由過期即路由的BD過期，將包含該BD地址的條目從鏈表中刪除。路由刪除時，需要重復路由查找過程，讀取全部有效路由，并逐條比對是否包含斷開鏈路。將包含斷開鏈路的BD地址條目從鏈表中剔除。刪除操作完成后，更新后一個條目的鏈表指針，使得鏈表完整。
2 實驗仿真與分析
2.1 總體功能仿真
圖4是路由存儲仿真結果。標號①是存儲的路由信息，store_route_en是路由存儲的使能，hop[31:0]路由數據周期數，did[31:0]目的節點地址，data_route[31:0]是路由數據。
圖5、圖6是路由查找仿真結果。did_to_rd_rt[31:0]是目的節點地址。標號③與標號④分別是存儲與讀取的路由數據，兩者是一樣的，故路由查找結果正確。
圖7與圖8是路由刪除仿真結果。標號①是存儲的路由，標號③是需要刪除路由包含的前端節點ID1與后端節點ID2地址。標號②是路由存儲時插入鏈表的有效BD地址，標號④是路由刪除后鏈表釋放的BD地址。兩者的數據一致，路由刪除結果正確。
2.2 總體性能仿真與分析
表1是一條路由存儲的時延隨周期變化的情況。由表1可知，隨著存儲的路由周期變長，模塊路由存儲的時延均在166.4 ns左右。
若路由不過期，每條路由固定長度且每次查找第一條存儲路由，表2是長度為2周期的路由查找時延隨著條數變化情況。表3是長度為8周期的路由查找時延隨著條數變化情況。
由表2、表3可知，路由周期固定，隨著存儲條數增加查找路由的時延快速增加。在路由表中存儲路由條數固定情況下，路由查找時延隨著路由長度的增加緩慢增加。路由查找的時延在ns級，說明查找速度很快。
表4是長度為2周期的路由刪除時延隨著條數變化情況。表5是長度為8周期的路由刪除時延隨著條數變化情況。
由表4、表5可知，在存儲周期固定的路由情況下，隨著存儲條數增加，刪除路由的時延快速增加，幾乎是2倍的速率。在路由表中存儲路由條數固定情況下，路由刪除時延隨著路由長度的增加緩慢增加。 但路由刪除的時延還在μs級以下，說明刪除速度依然很快。從路由存儲、查找、刪除的結果分析上來說，路由管理模塊工作效率是非常高的。
模塊設計使用vivado2015.2平臺，開發板采用Xilinx的VC707，使用的設備是XC7VX485T。片上總功耗為28.379 W，模塊功耗為11.755 W。片上各部分資源使用情況如表6所示。
由表6可見，使用硬件實現DSR路由表項管理所占用的硬件資源非常少，功耗十分小。
3 結論
本文針對在FPGA中支持DSR路由協議的核心內容路由表項管理提出了一種基于有限狀態機的設計與實現方法。建立實現模型，使用vivado2015.2平臺進行仿真，仿真結果很好地驗證了預期目標。通過實驗分析，發現使用FPGA實現DSR路由表項管理時延非常低，資源占用十分少，功耗很小。
參考文獻
[1] 王海濤.Ad Hoc網絡[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網絡DSR路由協議的優化設計[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] 陳勇.有限狀態機的建模與優化設計[J].重慶理工大學學報(自然科學)，2007，21(5)：55-58.
[9] 彼德·明斯，伊恩·艾利奧特，明斯，等.基于FSM和VerilogHDL的數字電路設計[M].北京：機械工業出版社，2016.
作者信息:
李 森，李 波，閆中江，楊 懋
(西北工業大學 電子信息學院，陜西 西安710072）