








摘 要: "在林、農作物監測作業中,可通過散布無線傳感器節點形成的自組織WSN收集作物環境信息。將UAV應用于分簇式WSN作為移動的數據收集sink節點,UAV不僅需要轉發各簇首節點的信息,還需轉發自帶傳感器檢測到的重要信息。為了保證UAV傳感器檢測信息及時轉發,并能夠進一步降低簇首節點能耗,延長WSN網絡壽命,提出異步帶優先級的數據轉發輪詢控制系統方案,應用馬爾可夫鏈和概率母函數進行建模分析系統性能。用自帶異步讀寫FIFO功能的FPGA作為主控器件,基于FPGA設計該輪詢系統硬件電路結構,驗證了該輪詢控制系統的可行性和高效性。實驗結果表明,該方案能保證UAV及時轉發重要數據,縮短服務延遲,提高WSN能耗效率,優化系統性能。
關鍵詞: "WSN-UAV; 輪詢模型; 優先級; 異步; 現場可編程門陣列; 能耗效率
中圖分類號: "TP391 """文獻標志碼: A
文章編號: "1001-3695(2022)02-026-0001-00
doi:10.19734/j.issn.1001-3695.2021.07.0279
Asynchronous polling system with priority data forwarding based on FPGA
Zhang Langfei, Li Shinan, Liang Zhuguan, Ding Hongwei
(School of Information, Yunnan University, Kunming 650500, China)
Abstract: "In forest and crop monitoring operations,crop environmental information can be collected by self-organizing WSN formed by spreading wireless sensor nodes.When the UAV is applied to the clustered WSN as the mobile sink node for data collection,the UAV not only needs to forward the information of each cluster head node,but also the important information detected by its own sensor.In order to ensure the timely forwarding of UAV sensor detection information,further reduced the energy consumption of cluster head node and prolonged the life of WSN network,this paper proposed an asynchronous data forwarding polling control system with priority,and used Markov chain and probability generating function to model and analyze the system performance.Using FPGA with asynchronous reading and writing FIFO function as the main control device,it designed the hardware circuit structure of the polling system based on FPGA,which verified the feasibility and high efficiency of the polling control system.Experimental results show that the proposed scheme can ensure timely transmission of important data by UAV,shorten service delay,improve WSN energy efficiency and optimize system performance.
Key words: "wsn-uav; polling; priority; asynchronization; FPGA; energy efficiency
0 引言
WSN(wireless sensor networks,無線傳感器網絡)采用分簇策略能夠改進網絡壽命[1,2],但選舉出的簇首節點不僅需要轉發簇內節點數據,還需要轉發鄰居簇首節點的數據到收集節點sink處,因此導致簇首節點能耗比較高,越靠近sink節點的簇首節點能耗就越高,簇首節點很容易因為能量消耗完而提前失效,從而影響整個WSN網絡壽命[3,4],若能降低簇首節點的能耗就可以大大提高整個WSN網絡的壽命。UAV(unmanned aerial vehicle,無人機)裝載有各種傳感器[5],具有成本低、應用方便、時效性強等優勢,被許多領域廣泛應用[6,7]。
輪詢模型作為一類經典通信模型,被廣泛應用于通信[8,9]和計算機網絡[10,11]。基本輪詢模型分為完全、門限和限定 K(K =1)三類服務策略,它包含三個主要過程,即服務對象的到達過程、服務臺的查詢轉換過程、服務臺的服務過程[12~14]。本論文針對UAV應用于分簇式WSN收集數據的場景改進傳統輪詢模型,UAV自帶的傳感器負責監測一些重要事件并通過UAV轉發到數據收集中心,簇首節點收集簇內節點數據,簇首節點的數據也通過UAV將轉發到數據收集中心,論文提出了異步帶優先級數據轉發輪詢控制方案。將UAV傳感器信息分組區分為高優先級隊列,WSN簇首節點信息分組區分為低優先級隊列,對同一隊列的查詢接收過程和處理轉發過程錯開適當的時序異步進行,以減小高優先級隊列的平均排隊等待服務時間,縮短系統平均時延。
FPGA有著低成本、開發周期短、可重構和并行運行等優點,已經被許多領域所應用[15,16]。Altera FPGA自帶讀寫雙時鐘FIFO,本文將其作為數據收發的主控器件。UAV與WSN的通信方式和UAV與數據收集中心的通信方式不同,UAV與簇首節點的通信采用與WSN兼容的低功耗方案,配置FPGA不同的通信通道并行控制UAV與WSN的通信和UAV與數據收集中心的通信,將查詢接受某個隊列數據與處理轉發該隊列的數據錯開合適的時序異步進行,實現該異步帶優先級的數據轉發輪詢控制系統方案,同時,應用FPGA直接調用物理層MOS管器件功能設計數據通道選擇控制電路[17],提高硬件電路運行速度。
1 系統建模分析
1.1 系統建模
WSN-UAV聯合應用于農、林業監測等作業中,UAV收集WSN數據的飛行過程中往往會在空中遇到一些突發緊急事故需要及時發送到數據收集中心。為了確保UAV監測到的緊急數據得到優先轉發服務,把UAV監測到的信息分組區分為高優先級隊列,簇首節點需要轉發的信息分組區分為低優先級隊列。設系統有 N 個簇首節點,UAV監測設備用 h 表示,各簇首節點用 i(i=1,…,N )表示,系統為監測設備 h 分配存儲器FIFO_h,其中存儲的信息分組定義為中心隊列 h ,為所有簇首節點分配存儲器FIFO_d,其中存儲的信息分組定義普通隊列 d ,如圖1所示。系統的運行過程及其工作條件如下:
a)到達過程。各隊列信息分組到達過程遵從相互獨立、同分布的隨機過程,普通隊列 i 到達過程的概率母函數、均值和方差為 A(z)、λ=A′(1)和σ2 λ=A″(1)+λ-λ2,中心隊列h到達過程的概率母函數、均值和方差分別為A(z)、λ h=A′ h(1)和σ λ2 h=A″ h(1)+λ h-λ2 h 。
b)轉換過程。隊列間的查詢過程由兩個異步過程構成。第一個過程是查詢UAV監測設備和各個簇首節點的過程,系統首先查詢UAV監測設備,然后查詢簇首節點 i(i=1,…,N )、UAV監測設備、簇首節點 i+1(i=1,…,N ),…,查詢完簇首節點 N ,又開始下一輪查詢過程;第二個過程是查詢存儲器FIFO_h和FIFO_d中的信息分組的過程,這個過程是在中心隊列和普通隊列之間查詢轉換的。設不同隊列間的查詢轉換時間服從一個相互獨立、同分布的概率,其概率母函數、均值和方差分別為 R(z)、r=R′(1)和σ2 r=R″(1)+r-r2 。
c)服務過程。系統的服務過程由兩個異步過程構成。第一個服務過程是接收信息分組存儲的過程,按照完全服務策略接收UAV監測設備 h 的信息分組存儲于FIFO_h,按照限定 K ( K =1)服務策略接收簇首節點 i ( i=1,2,…,N )信息分組存儲于FIFO_d,系統首先接收UAV監測設備 h 的信息分組,然后轉向接收簇首節點 i 的信息分組,又轉向接收UAV監測設備 h 的信息分組,再轉向接收簇首節點 i+1 ( i=1,…,N )的信息分組,…,當第 N 個簇首節點服務結束,系統又開始下一輪服務周期;第二個服務過程是處理并轉發存儲器FIFO_h和FIFO_d中的信息分組,系統首先采用完全服務策略處理轉發存儲器FIFO_h中的信息分組,當FIFO_h變空時,系統采用限定 K ( K =1)服務策略查詢處理轉發存儲器FIFO_d中的信息分組,當服務存儲器FIFO_d結束,系統又開始下一輪服務周期。
遵循先到先服務的規則,設處理一個普通隊列的信息分組的時間概率母函數、均值和方差分別為 B(z)、β=B′(1)和σ2 β=B″(1)+β-β2 ,設處理一個中心隊列信息分組的時間概率母函數、均值和方差分別為 B h(z)、β h=B′ h(1)和σ2 β h=B″ h(1)+β h -β2 h 。
描述系統狀態的變量的概率母函數推導如下。
設系統未達到飽和狀態,即滿足穩態條件 ρ d+ρ hlt;1(ρ d=λ d·β d , ρ h=λ h·β h )。
采用離散時間,設 t n 時刻系統開始為中心隊列 h 服務,系統在穩態條件下接著在 t* n時刻系統為普通隊列d服務,t n+1時刻再接著為中心隊列h 服務。
用 ξ d(n)和ξ h(n)分別表示t n 時刻普通隊列 d、 中心隊列 h 的信息分組數,因此,可定義 t n 時刻描述系統狀態變量的概率母函數為
G dh(z d,z h)= lim "n→∞ E[zξ d(n*) dzξ h(n*) h] ""(1)
則可推出在 t* n 時刻描述系統狀態變量的概率母函數為
G dh(z d,z h)= lim "n→∞ E[zξ d(n*) dzξ h(n*) h] =R(A h(z h)A d(z d)){ 1 z d "B d(A h(z h)A d(z d)) "[G d(z d,z h)-G d(z d,z h)| z d=0]+G d(z d,z h)| z d=0} ""(2)
同理可推導出 t n+1 時刻描述系統狀態變量的概率母函數為
G hd(z d,z h)= lim "n→∞ E[zξ d(n+1) dzξ h(n+1) h] =G dh(z d,B h(A d(z d)F h(A d(z d)))) ""(3)
F h(z) 表示采用完全服務策略處理中心隊列h的一個信息分組所用時間的概率母函數。
系統建模完成后,為體現方案的優越性,需要特定的指標對其進行量化分析,1.2節對指標的理論分析進行了詳細推導。
1.2 系統性能分析
用 g h(h)、g d(d) 分別表示中心隊列 h 和普通隊列 d 信息分組平均排隊隊長, E(w h) 、 E(w d) 分別表示中心隊列 h 、普通隊列 d 信息分組平均排隊等待服務時間,對式(2)(3)分別求一階、二階導,則有:
g h(h)= γλ h(1-ρ h) 1-ρ d-ρ h """(4)
g d(d)= γλ2 d 2(1-ρ d-ρ h-γλ d) { R′′ γ(1-ρ h) + B″ d γ - 2γ 1-ρ h + 2 λ d +
1 (1-ρ d-ρ h) [(1-ρ h) A″ d λ2 d +2ρ h+ β2 hA″ h 1-ρ h + 1-ρ h+ρ2 h 1-ρ h λ hB″ h]} "(5)
g h(h,h)=R″λ2 h+γA″ h+ γλ d 1-ρ d-ρ h (2γβ dλ2 h+λ2 hB″ d+β dA″ h) "(6)
E(W h)= g h(h,h) 2λ hg h(h) - A″ h(1) 2λ2 h(1+ρ h) + λ hB″ h(1) 2(1-ρ h) ""(7)
E[w d]= g d(d) λ2 d "- 1 λ d - A″ d(1) 2λ2 d """"(8)
其中: ""表示平均查詢周期,由 1-G d(z d,1)| z d=0= γ 1-ρ d-ρ h = "可得。
1.3 數值計算與仿真實驗
以時隙為時間單位,設信息分組到達過程服從泊松分布,使用MATLAB軟件平臺對該輪詢模型進行仿真分析,得到不同轉換時間 γ 、服務時間 β 條件下的平均排隊隊長和平均排隊等待服務時間與到達率的關系,并同理論公式的計算結果相對比,如圖2所示。
條件1的轉換時間 γ 、服務時間 β 取值分別都是條件2的2倍,而且圖1、2的橫坐標都是中心隊列的到達率取值,而普通隊列到達率取固定值0.2。由圖2可知:a)隨著到達率的不同變化,中心隊列在同一轉換時間 γ 和服務時間 β 的條件下,中心隊列的平均排隊隊長、平均排隊等待服務時間始終均明顯小于普通隊列的;b)減小轉換時間 γ 和服務時間 β ,普通隊列、中心隊列的平均排隊隊長和平均排隊等待服務時間都明顯變小。仿真結果充分說明該異步帶優先級的輪詢控制方案能保證對中心隊列優先服務的同時,還大大減小整個系統的服務延遲,提高系統的服務效率。
2 FPGA的電路設計與仿真驗證
2.1 系統結構
設計以FPGA為主控器件實現該異步帶優先級的輪詢控制系統主要由時鐘樹、異步FIFO、輪詢控制中心、處理等幾個功能模塊構成,如圖3所示。為了仿真驗證需要,還設計了信源和通道選擇控制兩個模塊。
2.2 信源模塊
采用ROM實現四個信源模塊分別模擬UAV監測設備、三個簇首節點,分別稱為信源h、信源1、信源2、信源3,應用仿真平臺產生隨機數功能模擬信息分組的到達過程。
2.3 數據通道選擇控制模塊
FPGA具有能夠直接調用物理層MOS管器件功能,調用MOS管器件設計CMOS傳輸門構成的四輸入數據通道選擇控制電路,控制各個信源與其對應的FIFO連通,如圖4所示。該方案與采用邏輯門的電路方案相比,能夠減少器件和連線,有利于提高電路運行速度[17]。
2.4 時鐘樹
時鐘樹模塊是將FPGA的主時鐘進行分頻,分別為FIFO_h、FIFO_d、異步帶優先級輪詢控制中心、處理模塊提供不同工作頻率的時鐘信號。
2.5 異步FIFO
設計兩個異步FIFO,分別稱為FIFO_h、FIFO_d。a)它們能夠同時進行讀寫操作,只要寫控制端信號有效,FIFO被寫入選中的信源模塊信息分組,只要讀控制端信號有效,FIFO讀出存儲的信息分組;b)通過輪詢控制模塊對FIFO的讀寫異步進行,不需要外掛存儲器就能夠滿足輪詢模型對存儲器足夠大的要求。
2.6 異步帶優先級的輪詢控制模塊
這個模塊組成輪詢系統的邏輯控制中心,這個模塊又分兩個子模塊,分別為帶優先級的接收控制模塊和帶優先級的處理控制模塊,在它們的輪詢控制下對同一隊列的接收和處理發送錯開一定時序異步進行。在帶優先級的接收模塊輪詢控制下,產生對FIFO的寫入控制信號以及各個信源到FIFO的數據通道選擇控制信號,如果選中信源 h ,其能夠發送所有信息分組存儲于FIFO_h中,如果選中信源 i(i=1,2,3 ),其最多只能發送一個信息分組存儲于FIFO_d中。在帶優先級的處理模塊輪詢控制下,邏輯控制中心產生對FIFO的讀出控制信號,如果選中FIFO_h,處理模塊讀取其所有信息分組進行處理和發送,如果選中FIFO_d,最多只能讀取一個信息分組進行處理和發送。
2.7 處理模塊
傳輸的每幀信息除數據信息外,還包括含有源地址和目標地址的幀頭、含有校驗信息的幀尾。處理模塊將幀頭、數據信息、校驗信息進行封裝發送。
2.8 仿真驗證
采用Verilog HDL語言設計硬件電路結構,應用Altera公司的Quarters II 軟件平臺進行仿真驗證。得到FIFO模塊和處理模塊信息分組的時序圖,如圖5所示。
在圖5中, date0、date1 分別表示FIFO_h、FIFO_d到達的信息分組, out_h、out_d 分別表示從FIFO_h、FIFO_d讀出的信息分組, out 表示進入處理模塊的信息分組。根據圖5,只要 date0 的信息分組不為空,系統控制讀出 date0 的信息分組直到其為空,然后才轉向讀出 date1 的一個信息分組,由此說明該基于FPGA的異步帶優先級的輪詢控制系統電路方案達到設計目的。
2.9 統計分析
根據系統模型,應用公式分別統計設計的電路方案中心隊列、普通隊列信息分組平均排隊隊長和平均排隊等待服務時間值。
中心隊列信息分組平均排隊隊長統計公式為
g h — = ∑ n c j=1 l h(j) n c """(9)
普通隊列信息分組平均排隊隊長統計公式為
g — "d= ∑ n c j=1 l d(j) n c """(10)
中心隊列信息分組平均排隊等待服務時間統計公式為
w — "h= ∑ M h k=1 w h(k) M h """(11)
普通隊列信息分組從屬站平均排隊等待服務時間統計公式為
w — "d= ∑ M d m=1 w d(m) M d """(12)
其中: n c 表示系統輪詢次數; l h(j)、l d(j)分別表示第j 次輪詢時中心隊列、普通隊列等待發送的信息分組數; M h、M d 分別表示中心隊列、普通隊列信息分組總數, w h(j)表示中心隊列第k 個信息分組的等待時間, w d(m)為普通隊列第m 個信息分組的等待時間。根據式(9)~(11)和(12),得到平均排隊隊長、平均排隊等待服務時間統計值并與式(4)~(7)(8)的理論值進行比較,如表1、2所示。其中 t m 為系統運行時間,單位為μs; g h、g d、w h、w d 表示理論值; g h — 、g d — 、w h — 、w d — "表示統計值。
從表1、2的結果來看,a)在相同的轉換時間 γ 和服務時間 β 下,中心隊列的平均排隊隊長和平均排隊等待服務時間均低于普通隊列的;b)當轉換時間 γ 和服務時間 β 變小時,中心隊列和普通隊列的平均排隊隊長和平均排隊等待服務時間均明顯減小。對設計電路進行仿真的結果進一步說明該異步帶優先級的輪詢控制方案能保證對中心隊列優先服務的同時,還大大減小了整個系統的服務延遲,提高了系統的服務效率。
3 與單片機方案比較
實現輪詢控制的電路方案有兩種,即單片機和FPGA。單片機雖然有多個I/O口,但它是串行處理多個設備輸入數據,也就是同一時間只能處理一個輸入設備數據。假設采用發送令牌方式在UAV與簇首節點之間建立通信,某個簇首節點一旦收到發送給自己的令牌,就發送其存儲器中的信息分組; 時間單位采用時隙,并假設各個通信階段所用時間為一個時隙,信息分組的長度為8位。兩種電路方案實現UAV轉發任意一個簇首節點的信息分組經歷的時段所用時間如表3所示。
表3中的“通信 1”表示UAV與簇首節點的通信,“通信2”表示UAV與數據收集中心的通信。從表3可以看出,采用FPGA的電路方案實現UAV轉發任意一個簇首節點的信息分組所用時間只有單片機的一半。
4 結束語
本文針對UAV-WSN聯合應用提出異步帶優先級的數據轉發輪詢控制方案,UAV傳感器設備信息分組區分為高優先級隊列,WSN簇首節點信息分組區分為低優先級隊列,應用不同的通信通道把接收和轉發過程錯開一定時序異步進行。應用馬爾可夫鏈和概率母函數對該異步帶優先級的數據轉發輪詢控制方案進行建模分析,推導出描述該異步帶優先級的輪詢控制系統性能的表達式,基于FPGA完成電路設計并通過仿真驗證,理論值和仿真值都說明:a)該輪詢控制系統能夠區分中心隊列的優先級,縮短對各個隊列的查詢服務時間,提高移動UAV的工作效率;b)由UAV與各簇首節點直接通信收集其數據,從而不需要簇首節點之間通信轉發數據而消耗能量,系統對各個隊列的查詢服務時間縮短,進一步減小簇首節點的能耗。
參考文獻:
[1] "The P T,Mai B H,Tuan N T, et al. Improving distributed energy efficient clustering algorithm to save lifetime for heterogeneous WSN[J]. International Journal of Computer Networks and Communications ,2017, 9 (4):81-96.
[2] Prince R,Pragya D.Optimized and load balanced clustering for wireless sensor networks to increase the lifetime of WSN using MADM approaches[J]. Wireless Networks ,2020, 26 (1):215-251
[3] 李東林,韋素媛.基于簇首位置控制的異構WSN分簇路由算法[J].微電子學與計算機,2018, 35 (5):74-78,83. (Li Donglin,Wei Suyuan.Clustering routing algorithm for heterogeneous WSN based on cluster head position control[J]. Microelectronics amp; Computer ,2018, 35 (5):74-78,83.)
[4] 蔣華,王瑤,王慧嬌,等.基于模糊邏輯的WSNs能量高效分簇路由算法[J].微電子學與計算機,2020, 37 (7):25-30. (Jiang Hua,Wang Yao,Wang Huijiao, et al. "Energy efficient clustering routing algorithm for WSNs based on fuzzy logic[J]. Microelectronics amp; Computer ,2020, 37 (7):25-30.)
[5] 高尚文,祖家奎,陶德臣.無人機綜合檢測與仿真系統[J].計算機系統應用,2020, 29 (10):68-74. (Gao Shangwen,Zu Jiakui,Tao Dechen.Unmanned Aerial Vehicle Integrated Detection and Simulation System[J]. Computer System Application, 2020, 29 (10):68-74.)
[6] 昂海松.無人機系統概念和關鍵技術[J].無人系統技術,2018, 1 (1):66-71. (Ang Haisong.Concept and key technologies of unmanned aerial vehicle system[J]. Unmanned Systems Technology ,2018, 1 (1):66-71.)
[7] 呂游.無人機系統適航現狀及發展研究[J].航空制造技術,2014(22):138-140,145. (Lyu You.Research on airworthiness status and development of uav system[J]. Aeronautical Manufacturing Technology ,2014(22):138-140,145.)
[8] 何敏,吳幫呂,孫飛飛,等.車載自組網V2I通信中可休眠輪詢接入控制策略性能分析[J].東南大學學報:自然科學版 ,2020, 50 (1):39-45. (He Min,Wu Banglyu,Sun Feifei, et al. "Performance analysis of dormancy polling access control strategy in vehicle-Ad hoc V2I communication[J]. Journal of Southeast University:Natural Science Edition ,2020, 50 (1):39-45.)
[9] 梁竹關.離散時間完全服務兩級輪詢系統理論研究[D].昆明:云南大學,2010. (Liang Zhuguan.Theoretical research on discrete time full service two-level polling system[D].Kunming:Yunnan University,2010.)
[10] 韓朋花,葉青,姜曉明,等.改進加權輪詢負載均衡算法研究[J].長春理工大學學報:自然科學版,2018, 41 (3):131-134. (Han Penghua,Ye Qing,Jiang Xiaoming, et al. "Research on improved weighted polling load balancing algorithm[J]. Journal of Changchun University of Science and Technology:Natural Science Edition ,2018, 41 (3):131-134.)
[11] 劉龍軍,丁洪偉,柳虔林,等.基于FPGA WSN輪詢接入控制協議的研究[J].通信學報,2016, 37 (10):181-187. (Liu Longjun,Ding Hongwei,Liu Qianlin, et al. "Design of polling access control protocol in WSN based on FPGA[J]. Journal of Communications ,2016, 37 (10):181-187.
[12] 孫洋洋,楊志軍.完全服務輪詢控制系統分析研究[J].湖北民族學院學報:自然科學版,2018, 36 (3):335-338,360. (Sun Yangyang,Yang Zhijun.Research on full service polling control system[J]. Journal of Hubei University for Nationalities:Natural Science Edition ,2018, 36 (3):335-338,360.)
[13] 羅啟鵬,保利勇,丁洪偉,等.離散時間并行優化門限服務輪詢系統排隊特性解析[J].電子學報,2019, 47 (9):1937-1942. (Luo Qipeng,Bao Liyong,Ding Hongwei, et al. "Analysis of queuing characteristics of discrete time parallel optimization threshold service polling system[J]. Acta Electronica Sinica ,2019, 47 (9):1937-1942.)
[14] 路秀迎,丁洪偉,楊志軍,等.限定 K =1非對稱輪詢系統的FPGA實現[J].自動化與儀表,2018, 33 (10):5-10. (Lu Xiuying,Ding Hongwei,Yang Zhijun, et al. FPGA implementation of limited "K =1 asymmetric polling system[J]. Automation amp; Instrumentation ,2018, 33 (10):5-10.)
[15] 余樂,李任偉,王瑤,等.綜述:面向SoC-FPGA的開源處理器[J].電子學報,2018, 46 (4):992-1004. (Yu Le,Li Renwei,Wang Yao, et al. "Review:open source processor for SoC-FPGA[J]. Acta Electronica Sinica ,2018, 46 (4):992-1004.)
[16] 任夢茹,侯宏錄.基于FPGA的實時雙目圖像采集與預處理系統設計[J].自動化與儀表,2020, 35 (1):58-61,75. (Ren Mengru,Hou Honglu.Design of real-time binocular image acquisition and preprocessing system based on FPGA[J]. Automation amp; Instrumentation ,2020, 35 (1):58-61,75.)
[17] 梁竹關,趙東風.MOS集成電路設計[M].北京:科學出版社,2011:88-89. (Liang Zhuguan,Zhao Dongfeng.MOS integrated circuit design[M].Beijing:Science Press,2011:88-89.)