限定K=1非對稱輪詢系統的FPGA實現

路秀迎，丁洪偉，楊志軍，保利勇，何 敏

（云南大學 信息學院，昆明 650500）

無線傳感器網絡WSN（wireless sensor network）是由大規模隨機分布在監控區域的微型傳感器節點組成的以數據為中心的任務型網絡，媒體接入控制 MAC（media access control）協議是聯接 WSN物理層與網絡層的紐帶，是保證節點之間高效通信的重要因素。

文獻[1-8]基于概率母函數與嵌入式馬爾可夫鏈的方法就平均排隊隊長、輪詢周期、等待時延等性能指標對對稱式輪詢系統展開分析，忽略了多樣性業務的信息非對稱性與服務器處理差異性，僅適用于單一服務類型的網絡應用，大大限制了該技術的使用范圍和適用空間。研究非對稱輪詢系統對WSN多業務應用具有重要的理論意義與研究價值[9]。

FPGA基于硬件并行機制工作，具有半定制、非固化的特點，控制靈活，開發周期短，運行速度相比傳統串行計算CPU提高近100倍[10]，可將其作為異構加速資源應用于WSN，實現節點數據的實時處理，滿足了非對稱WSN在軟硬件延展性、可移植性方面的要求。

系統采用限定K=1服務策略進行輪詢調度，保證了簇內傳感器節點之間訪問介質的公平性。基于QUARTUSⅡ平臺進行功能測試，并對系統性能展開理論與統計分析，結果表明該非對稱輪詢系統能夠滿足多樣性業務服務質量的彈性要求，具有更好的普適性。

1 理論介紹

非對稱限定K=1輪詢系統的基本模型如圖1所示，系統由1個中央控制器與N個排隊隊列（終端）組成，各終端隨機變量所服從的概率分布不同，具體表現為以下幾點：

圖1 非對稱輪詢系統示意Fig.1 Schematic diagram of asymmetric polling system

（1）到達各終端的信息分組服從泊松分布，其到達速率λi表示i號終端單位時間內接收到信息分組的個數。終端之間信息分組到達率的隨機變量λi相互獨立且遵從不同的概率分布。其分布的概率母函數、均值、方差分別是

（2）各終端的服務時間βi表示各終端發送單位信息分組需要的時間，各終端服務時間的隨機變量βi相互獨立且服從不同的概率分布。其分布的概率母函數、均值、方差分別是

（3）控制器訪問空閑終端i或服務完終端i后經過時間γi查詢訪問終端i+1，相鄰終端之間的轉換時間的隨機變量γi相互獨立且服從不同的概率分布。其分布的概率母函數、均值、方差分別為R（z），

中央控制器按照物理連接的邏輯順序對各終端進行輪詢訪問，訪問到的非空終端享有信息發送權，否則經過設定的轉換時間訪問下一終端。獲得服務權限的終端按照限定K=1的服務規則發送數據，即每次只發送該終端緩存的1個信息分組。

評估輪詢系統性能的參數主要有平均排隊對長和平均時延，文中采用內嵌馬爾可夫鏈與概率母函數的方法對系統展開理論分析，定義的隨機變量有：vi（n）為服務器對 i號終端服務的時間，ui（n）為服務器從第i號終端轉向第i+1號終端的輪詢轉換時間，μj（ui）為在 ui（n）時間內進入第 j號終端的信息分組數，ηj（vi）為在 vi（n）時間內進入第 j號終端中的信息分組數。定義隨機變量ξi（n）為第i號終端站點在tn時刻其存儲器內存儲的信息分組數，各終端服務強度 ρi（ρi=λiβi）。 那么排隊系統在 tn時刻的狀態可表示為［ξ1（n），ξ2（n），…，ξN（n），ξh（n）］，分布函數為

定義gi（j）為tn時刻第i號節點接受服務時，第j號節點平均存儲信息分組數，則有：

式中：i=1，2，…，N；j=1，2，…，N。

定義：

對式（1）求二階偏導可得：

由式（5）～式（8）求得：

圖2～圖4分別為非對稱限定K=1服務輪詢系統的性能參數與到達率、服務時間、轉換時間之間的關系圖。圖2 中 N=4，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4；圖3 中N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01， β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4； 圖4 中 N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ2=1，γ3=3，γ4=4。

2 硬件實現

圖2 系統性能參數與到達率的關系Fig.2 Relation between system performance parameters and arrival rate

圖3 系統性能參數與服務時間的關系Fig.3 Relation between system performance parameters and service time

圖4 系統性能參數與轉換時間的關系Fig.4 Relation between system performance parameters and conversion time

設計中按照WSN簇內通信的工作原理、采用“自頂向下”的設計方法把系統分為信源、節點、控制、接收4個模塊部分進行硬件設計，圖5為系統設計框圖，表1為非對稱系統相關參數值。

圖5 系統設計框圖Fig.5 Block diagram of the system

表1 系統設定參數值Tab.1 Values of the system parameters

2.1 信源模塊

信源模塊用于產生滿足馬爾科夫特性的信息分組，但在FPGA時序電路中難以實現“單位時隙產生具有泊松特性的多個信息分組”的精確控制，故設計中利用分頻技術并借助Matlab工具產生泊松文檔協同解決這一難題。利用自加1計數器原理設計地址譯碼電路，使得RAM在50 MHz時鐘源觸發下讀取泊松分布.mif文檔并完成原始信息在時序電路中的映射轉換，為便于區分，設計中基于計數器原理將讀取到的λ數值映射到電路中的λ個報文分組10 100 110，無效信息分組則轉換為00 000 000，信源產生的原始數據混合了有效信息分組與無效信息分組。

2.2 節點模塊

非對稱輪詢系統中服務器對各終端業務服務效率不同，各終端實時緩存到達信息分組并在獲得服務權限時按照FCFS順序發送，實現時通過調用FPGA異步fifo解決讀寫過程的速度匹配問題和獨立控制問題，其工作流程分緩存與發送兩部分分別進行描述。

2.2.1 緩存功能

終端緩存信息分組過程即該終端dcfifo寫入過程，各終端寫時鐘源皆為50 MHz時鐘源，其工作過程：

（1）信源產生的混合數據經過濾波電路，檢測到有效信息分組置寫使能信號有效，否則無效；

（2）寫使能信號有效時，dcfifo在寫時鐘源觸發下把相應的有效數據寫入存儲器，從根本上杜絕了信息冗余問題。

2.2.2 發送功能

非空節點獲得服務權限后按照 “先到先出”的順序發送已緩存數據，其讀時鐘源頻率特性與系統設定服務時間一致，其工作流程：

（1）根據控制信號與dcfifo工作特性設置下溢保護電路，防止存儲器讀空；

（2）節點服務信號有效時，dcfifo開始輸出數據；

（3）各節點設置限定指示器，通過邊緣檢測判定該節點進入服務狀態后，根據服務時間與系統工作頻率特性設計計數器，保證該節點發送一個信息分組（即經過單位服務時間）后指示器指示信號為由高電平變為低電平，結束當前服務。圖6為終端1限定指示器工作流程。

2.3 數據融合

輪詢系統基于資源共享理論控制各節點無競爭接入網絡，保證同一時間內只有1個通信節點占用信道，有效避免了各終端發送數據的碰撞問題。簇首接收到簇內節點的數據后按照相應的算法進行融合發送至總線上。

圖6 限定指示器工作流程Fig.6 Work flow chart of the limited indicator

2.4 控制模塊

按照WSN簇內輪詢控制原理，利用有限狀態機在控制模塊分別設置了4個節點服務狀態與4個相鄰節點輪詢轉換狀態， 分別記為 s1，s2，s3，s4，jishu1，jishu2，jishu3，jishu4。 圖7 為控制模塊的狀態轉移圖，其中各狀態表示：

sn：站點 n服務狀態，高電平有效；jishun：相鄰站點間轉換狀態；Crn：站點n限定指示器指示信號；Cntn：相鄰站點間轉換時間計時信號；kn：站點nFIFO空信號。

圖7 控制模塊狀態轉移圖Fig.7 State transition diagram of the control module

其具體工作過程：

（1）轉換時間γi到，控制器訪問站點i+1的存儲容量，若該容量顯示非0，系統進入si+1服務狀態，否則進入jishui+1的轉換狀態。

（2）若站點i+1進入si+1服務狀態，控制器根據該終端限定指示信號控制狀態轉移，若指示信號cri+1為低電平，系統進入γi+2的轉換狀態，否則表示該終端的1個信息分組尚未發送完成，系統繼續si+1的服務狀態。

2.5 接收模塊

接收模塊利用同步控制信號進行各節點發送數據信息的恢復，系統發送部分控制信號包含節點傳輸信息分組的時序信息，在接收端用同步控制信號作為同步fifo寫使能信號便可從總線數據中正確恢復出各節點數據信息。

3 實驗結果

按照上述硬件實現描述方法，對FPGA非對稱限定服務輪詢系統編譯后于QUARTUSⅡ進行功能仿真，圖8為系統仿真圖。

圖8 系統仿真圖Fig.8 System simulation diagram

仿真圖中clk信號是系統時鐘，clk1是clk四分頻后的時鐘信號，也是系統工作的基準時鐘；cp信號是服務器輪詢相鄰站點的轉換時間信號，高電平有效；s信號是站點服務信號，高電平有效；cr信號為限定指示器的繼續讀取信號，高電平有效；d信號是服務器輸出信號；r信號是接收端恢復信號；pbus信號是總線信號；use信號是各站點存儲器緩存的數據容量信號；

由仿真圖得：

（1）各終端的服務時間設定值是 4、2、1、2，限定指示器在檢測到服務信號有效后變為高電平，在相應節點單位服務時間到達前電平置低?？刂颇K在時鐘源觸發下檢測到cr信號失效后置其服務信號為低電平。仿真圖中發送單位信息分組占據時隙數與設定值一致，表明系統實現了限定K=1服務規則的要求。

（2）系統服務過程中各終端服務信號與其輸出信號在時鐘控制下同步動作，高電平有效，相應的終端輸出信息分組，實現了各終端存儲器緩存與發送的功能。

（3）輪詢系統工作過程分為相鄰站點轉換過程與站點服務過程，圖中cp信號與s信號交互出現，cp信號占據時隙個數分別為2、1、3、4，驗證了控制模塊設計的正確性；

（4）系統接收信號與發送信號一致，時間延時2時隙，實現了系統對發送數據的正確接收功能。

表2～表3為系統性能參數（平均排隊對長與平均時延）理論值與統計值的對比表。

表2 各節點平均排隊隊長理論值與統計值對比表Tab.2 Comparison of theoretical value and statistical value of average queue length of each node

表3 各節點平均時延統計值與理論值對比表Tab.3 Comparison of theoretical value and statistical value of average time delay of each node

根據表2～表3中，得出：

（1）系統參數統計值與理論值在誤差允許范圍內相一致，驗證了設計的可行性與正確性；

（2）系統各節點平均排隊隊長與平均時延均隨著到達率增加而提高，不會出現高并發忙碌節點的相位滯留，反映了系統為各節點提供服務的公平性；

（3）各節點平均排隊隊長與平均時延均隨著到達率增加而非線性提高，這是由于系統節點工作的非對稱性決定的，更適用于多業務應用。

4 結語

本文根據WSN網絡應用中服務類型多樣化、信息傳遞不對稱的工作特點，首次基于FPGA對非對稱限定K=1輪詢系統進行了硬件實現，對系統信息分組到達率、服務時間、轉換時間等工作特性參數設置非一致性數值，采用限定K=1服務策略實現WSN的輪詢MAC層控制，保證了簇區域內節點之間介質訪問的公平性，時延特性優良。功能測試與統計分析結果驗證了設計的可行性，穩定性強，可拓展性高，對WSN多業務應用有更大的實用價值。