3.2 可靠數(shù)據(jù)分發(fā)協(xié)議的設計

　　在闡述具體的設計思路之前，先提出以下應用場景的假設。

　　假設一：網(wǎng)絡節(jié)點不支持高級的操作系統(tǒng)?？梢岳斫鉃楸仨毧紤]節(jié)點處理和通信能力有限，而且通信協(xié)議要從底層(如MAC層)實現(xiàn)。

　　假設二：大部分待燒錄節(jié)點分布在數(shù)據(jù)基站的通訊范圍之內(nèi)?？梢岳斫鉃橥ㄐ艆f(xié)議不需要實現(xiàn)復雜的多跳通信和流水線，可以充分利用數(shù)據(jù)基站第一次數(shù)據(jù)廣播，這一點下文會詳細闡述。

　　基于以上兩點假設，可靠性數(shù)據(jù)分發(fā)協(xié)議的具體設計如下。

　　考慮到不同平臺的無線收發(fā)模塊提供的服務接口和通信質(zhì)量的差異以及程序更新對網(wǎng)絡可靠性的要求，通信協(xié)議選擇在網(wǎng)絡層實現(xiàn)可靠數(shù)據(jù)分發(fā)的機制，協(xié)議只需要硬件平臺在MAC層提供收發(fā)數(shù)據(jù)幀的應用接口即可。協(xié)議中，數(shù)據(jù)分發(fā)分為兩個階段：第一輪發(fā)送階段和節(jié)點間交流階段。圖4.2為兩個階段通信方式示意圖。

　　(實線代表發(fā)送完整數(shù)據(jù)文件，虛線表示發(fā)送數(shù)據(jù)頁)

　　1、第一輪發(fā)送階段。

　　數(shù)據(jù)基站(如PC)在接收節(jié)點準備好后不間斷廣播數(shù)據(jù)幀，直至數(shù)據(jù)發(fā)送結(jié)束;接收節(jié)點盡力接收數(shù)據(jù)，并記錄自己已有數(shù)據(jù)幀的id信息，期間不向源節(jié)點發(fā)送反饋信息。

　　在原始的Deluge協(xié)議中沒有這一階段，因為Deluge協(xié)議中可能無線傳感器網(wǎng)絡龐大，分布范圍也較廣，所以數(shù)據(jù)分發(fā)一旦啟動，所有接收到數(shù)據(jù)的節(jié)點都參與到數(shù)據(jù)發(fā)送中來;而本設計中，網(wǎng)絡充分利用了假設二中的節(jié)點分布條件，通常情況下，在第一輪發(fā)送結(jié)束后，相當大比例的節(jié)點就已經(jīng)接收到了大部分的數(shù)據(jù)，而這個過程中因為只有數(shù)據(jù)基站在發(fā)送廣播，網(wǎng)絡中數(shù)據(jù)傳輸?shù)男适亲罡叩?。當然，這種節(jié)點分布條件不滿足的情況也不會明顯降低數(shù)據(jù)分發(fā)效率。

　　節(jié)點間交流階段。

　　交流階段參考了trickle算法的“polite gossip”策略，所有節(jié)點(包括數(shù)據(jù)基站)都參與到交流中去。每個節(jié)點的交流的目的都是相同的，即將自己擁有的數(shù)據(jù)包發(fā)送給需要的節(jié)點和請求并接收自己需要的數(shù)據(jù)包。

　　第2階段是保證可靠性的關鍵，協(xié)議中讓源節(jié)點也參與到交流中來，這是為了防止網(wǎng)絡狀況極差以至在第一輪發(fā)送結(jié)束之后所有節(jié)點接收數(shù)據(jù)的總和都不構(gòu)成完整數(shù)據(jù)文件的極端情況。這一步中，節(jié)點長時間處于“維護”狀態(tài)標志數(shù)據(jù)分發(fā)結(jié)束。

　　節(jié)點首先廣播廣告，每一個廣告包含一個摘要(φ)，摘要(φ)由兩部分組成：(1)本節(jié)點的IP標識v。(2)本節(jié)點的最大可用頁號p，即φ(v,p)?？捎庙撎杙的定義：頁p所包含的包被節(jié)點全部接收，稱頁p完成。頁p被完成并且它之前的所有的頁(0,p)也被節(jié)點全部接收，稱頁p可用。節(jié)點通過廣告來了解對方擁有的數(shù)據(jù)信息，繼而向比自己數(shù)據(jù)更完備的節(jié)點發(fā)送數(shù)據(jù)頁請求。協(xié)議中將時間分成時間片(round)，在每一個時間片中，節(jié)點來決定是否廣播一個廣告。假設時間片的長度由Tm,i來表示，它的上下界由Tl和Th來表示，則有取Tl

　　交流階段中，節(jié)點擁有“維護”、“請求”和“發(fā)送”中的人一個狀態(tài)。節(jié)點在“維護”狀態(tài)廣播廣告并聽取其他節(jié)點的廣播;在請求階段向其他節(jié)點發(fā)送數(shù)據(jù)頁請求，并接收對方發(fā)來的數(shù)據(jù);在發(fā)送狀態(tài)廣播被請求的數(shù)據(jù)頁。圖4.3為狀態(tài)轉(zhuǎn)換示意圖。主要的交流規(guī)則如下。

　　(1)“維護”狀態(tài)規(guī)則

　　M1: 假設時間片i的開始時間為ti，節(jié)點在ti+ri的時間段內(nèi)，若接收不到廣告φ'=φ，則廣播廣告φ;若收到與φ不一致的廣告(包括φ'=φ、廣告幀和數(shù)據(jù)幀等)，則調(diào)整時間片為Tl，并立即重新開始時間片;若接收到廣告φ'=φ，則調(diào)整時間片為min(2*Tm,i ,Th )。

　　M2: 節(jié)點在收到廣告φ'(v',p')中p'大于自身的最大可用頁p時，轉(zhuǎn)向“請求”狀態(tài)，向節(jié)點v'發(fā)送數(shù)據(jù)頁請求;節(jié)點收到請求幀，則轉(zhuǎn)向“發(fā)送”狀態(tài)，廣播被請求數(shù)據(jù)頁。

　　規(guī)則1能控制冗余廣告的發(fā)送，節(jié)約網(wǎng)絡資源，并且根據(jù)網(wǎng)絡狀況動態(tài)調(diào)整時間片長度，從而是網(wǎng)絡資源得到有效的利用。

　　規(guī)則2實現(xiàn)從“維護”狀態(tài)到“請求”和“發(fā)送”狀態(tài)的轉(zhuǎn)換。

　　(2)“請求”狀態(tài)規(guī)則：

　　M3：若節(jié)點在向源節(jié)點發(fā)出數(shù)據(jù)頁請求后節(jié)點在時間t(t為自定義時間長度，是經(jīng)驗值，根據(jù)網(wǎng)絡狀況而定)內(nèi)沒有收到數(shù)據(jù)，則再次發(fā)送請求，若累計請求次數(shù)大于k(k為自定義次數(shù))，則認為請求失敗，返回“維護”狀態(tài);若節(jié)點接收到數(shù)據(jù)頁，則在接收結(jié)束后返回“維護”狀態(tài)。

　　規(guī)則3中考慮到網(wǎng)絡的質(zhì)量因素，定義了等待時間t和最大請求次數(shù)k。

　　(3)“發(fā)送”狀態(tài)規(guī)則：

　　M4：節(jié)點進入“發(fā)送”狀態(tài)立即廣播被請求的數(shù)據(jù)頁，廣播結(jié)束后返回“維護”狀態(tài)。

　　規(guī)則4中要注意的是，節(jié)點以廣播的方式發(fā)送數(shù)據(jù)，這意味著處于“請求”狀態(tài)的節(jié)點可以接收任何節(jié)點(不一定是它請求的指定節(jié)點)發(fā)送的符合其需要的數(shù)據(jù)包，這也是協(xié)議中避免網(wǎng)絡冗余的一個體現(xiàn)。

　　以上是本設計中可靠數(shù)據(jù)分發(fā)協(xié)議的全部內(nèi)容，本文在下一節(jié)中將詳細論述協(xié)議的軟件設計實現(xiàn)。

　　3.3 可靠數(shù)據(jù)分發(fā)協(xié)議的軟件設計實現(xiàn)

　　協(xié)議的軟件設計在網(wǎng)絡層實現(xiàn)，涉及到MAC層接口的調(diào)用。本節(jié)先簡單介紹本設計實驗平臺上網(wǎng)絡模塊提供的MAC層應用接口，然后詳細論述軟件的設計和實現(xiàn)。

　　3.3.1 MAC層接口簡介

　　首先做兩點說明。

　　第一，設計中使用的MAC層接口不提供絕對可靠的網(wǎng)絡通信。一方面是因為設計使用實驗室自制的硬件平臺主要用于做群體實驗，而群體實驗不需要可靠的網(wǎng)絡通信，所以平臺的通信模塊也沒有能實現(xiàn)可靠通信的機制;另一方面要求MAC層提供可靠通信也不是必要的。

　　第二，網(wǎng)絡層只使用了MAC層提供的數(shù)據(jù)幀發(fā)送和數(shù)據(jù)幀接收兩個接口，網(wǎng)絡層的幀結(jié)構(gòu)包含在MAC數(shù)據(jù)幀的數(shù)據(jù)域中。

　　從第一點可以看到，協(xié)議在網(wǎng)絡層實現(xiàn)可靠數(shù)據(jù)傳輸?shù)臋C制，降低了對MAC層通信質(zhì)量的要求，而第二點說明協(xié)議僅僅需要MAC層提供兩個最基本的應用接口。本設計中的可靠數(shù)據(jù)分發(fā)協(xié)議對底層通信的要求很低，具有較好的魯棒性和可移植性。

　　本設計實驗平臺上提供的MAC層數(shù)據(jù)幀發(fā)送命令結(jié)構(gòu)如圖4.4所示，其中區(qū)域3為數(shù)據(jù)域，包含網(wǎng)絡層的幀結(jié)構(gòu)，另外節(jié)點在MAC層以廣播的方式通信，所以命令中不包含源節(jié)點和目的節(jié)點的地址信息。MAC層接收到數(shù)據(jù)幀后，將數(shù)據(jù)域分離出來存儲到接收緩存區(qū);發(fā)送數(shù)據(jù)時，將發(fā)送緩存區(qū)中的數(shù)據(jù)加上MAC層數(shù)據(jù)幀的頭部和尾部并發(fā)送出去，網(wǎng)絡層只關心發(fā)送和接收緩沖區(qū)中的數(shù)據(jù)。這里規(guī)定以下章節(jié)中提到的各種幀結(jié)構(gòu)均指網(wǎng)絡層幀結(jié)構(gòu)。

　　3.3.2 可靠數(shù)據(jù)分發(fā)協(xié)議的數(shù)據(jù)結(jié)構(gòu)設計

　　網(wǎng)絡層數(shù)據(jù)要經(jīng)過緩存，解析再到存儲或者執(zhí)行三步操作，并且不同種類的幀要區(qū)別處理，因此一個好的數(shù)據(jù)結(jié)構(gòu)設計方案對簡化數(shù)據(jù)處理操作和提高數(shù)據(jù)處理效率是非常有必要的。圖4.5為網(wǎng)絡層數(shù)據(jù)流圖，數(shù)據(jù)幀的流向為：

　　從MAC層讀入后放入原始數(shù)據(jù)緩沖區(qū);

　　經(jīng)解析后得到幀結(jié)構(gòu);

　　將幀結(jié)構(gòu)作相關處理后僅提取頁號(p)、幀號(id)和數(shù)據(jù)(data)放到寫flash緩沖區(qū);

　　寫flash。

　　注意以上是數(shù)據(jù)幀的流向，除數(shù)據(jù)幀以外的其他類型幀(如請求幀，結(jié)束幀等)只執(zhí)行第(1)、(2)步操作。下面著重論述圖中每個階段涉及到的數(shù)據(jù)結(jié)構(gòu)。[!--empirenews.page--]

　　緩沖區(qū)Deluge_buf

　　Deluge_buf是一個環(huán)形緩沖區(qū)，用于緩存原始的網(wǎng)絡層數(shù)據(jù)。緩沖區(qū)實際上是由一個環(huán)形鏈表、兩個指針和一個整數(shù)組成。鏈表的每個節(jié)點用于存儲實際數(shù)據(jù)，節(jié)點數(shù)目根據(jù)需要而定;一個tail指針和一個head指針，分別指鏈表的讀出點和寫入點，執(zhí)行一次讀出或?qū)懭氩僮骱?，tail或head指針都向前移動一次，整數(shù)的作用是統(tǒng)計當前鏈表上可用節(jié)點的數(shù)目。Deluge_buf結(jié)構(gòu)體定義如下：

　　struct Deluge_buf {

　　struct data_entry queue_data[QUEUE_LENGTH]; // The data of current queue

　　uint8 recv_num;

　　uint8 queue_head;

　　uint8 queue_tail;

　　};

　　值得注意的是結(jié)構(gòu)體data_entry中Payload項的組成在不同類型的幀中是不同的，比如數(shù)據(jù)幀中Payload包括頁號p、幀號id和數(shù)據(jù)data以及數(shù)據(jù)長度data_len，而廣告幀中只包含p和id，因此解析方法要根據(jù)type值來區(qū)分。

　　幀結(jié)構(gòu)DelugeData

　　如圖五所示，DelugeData定義了幀類型(type)等六個數(shù)據(jù)項，設計中根據(jù)不同的幀類型規(guī)定了各個數(shù)據(jù)項的含義，具體定義如表4.1所示，“—”表示該數(shù)據(jù)項在幀中沒有定義。

表4.1 DelugeData中數(shù)據(jù)項含義的定義

　　3、緩沖區(qū)Flash_buf

　　因為寫flash操作比網(wǎng)絡傳輸慢得多，為了避免寫flash拖慢整個數(shù)據(jù)分發(fā)速度，建立緩沖區(qū)Flash_buf用于緩存準備好的數(shù)據(jù)。Flash_buf也是一個環(huán)形緩沖區(qū)，原理和Deluge_buf相同。緩沖區(qū)的節(jié)點包含p、id、data三個數(shù)據(jù)項和指針域next，其中data是要寫入flash的數(shù)據(jù)，p和id用于計算待寫入的flash地址。

　　3.3.3 可靠數(shù)據(jù)分發(fā)協(xié)議的軟件架構(gòu)設計

　　可靠數(shù)據(jù)分發(fā)協(xié)議的軟件構(gòu)架設計包括發(fā)送端和接收端兩塊內(nèi)容。發(fā)送端軟件運行在數(shù)據(jù)基站上，分為兩個階段，第一階段通知節(jié)點連續(xù)地發(fā)送整個文件，第二階段運行狀態(tài)機參與到節(jié)點的交流中去;接收端軟件運行在待燒錄節(jié)點上，第一個階段盡可能多的接收基站發(fā)送來的數(shù)據(jù)，第二階參與節(jié)點間討論。因為發(fā)送端第一階段軟件比較簡單，第二階段和接收端相同，所以這里只重點介紹接收端的軟件構(gòu)架設計。

　　第一階段：

　　程序完成初始化后進入準備接收狀態(tài)，當數(shù)據(jù)幀到來時將數(shù)據(jù)提取出來寫到flash相應的地址(地址由頁號p和幀號id計算得到)，并將該幀標記為“完成幀”;若接收到結(jié)束幀，則記錄結(jié)束幀的頁號pmax和幀號idmax并進入第二階段;若接收到其他類型幀則直接進入第二階段。第一階段的軟件流程圖如圖4.6所示。

　　第二階段：

　　完成第一輪接收后，程序運行ADV-REQ-DATA狀態(tài)機，和其他節(jié)點交流，完善或幫助其他節(jié)點完善數(shù)據(jù)文件。狀態(tài)機分為MAINTAIN(維護)、RX(請求)和TX(發(fā)送)三個狀態(tài)，程序首先進入MAINTAIN狀態(tài)。MAINTAIN狀態(tài)下，程序監(jiān)聽廣告幀和請求幀并在適當時機發(fā)送廣告，根據(jù)協(xié)議規(guī)定，程序可能跳轉(zhuǎn)到RX狀態(tài)或TX狀態(tài)進行數(shù)據(jù)幀請求和發(fā)送操作，操作完成后返回MAINTAIN狀態(tài)。程序中定義一個最長時間tmax，如果MAINTAIN狀態(tài)持續(xù)時間超過tmax，則認為整個數(shù)據(jù)分發(fā)過程結(jié)束，程序檢查自己接收到的數(shù)據(jù)是否完備后退出。第二階段的軟件流程圖如圖4.7所示。

　　四 系統(tǒng)測試

　　本測試將用三個程序作為用例，以測試系統(tǒng)的可用性。三個程序分別為：

　　Led.bin實現(xiàn)簡單的跑馬燈;

　　GoAhead.bin 三輛小車將一直向前方走，即使碰到障礙物也不停止;

　　RandomWalk.bin 三輛小車將進行隨機行走，并且碰到障礙物后會進行壁障，轉(zhuǎn)彎。

　　首先我們將批量更新跑馬燈的程序，然后我們來看GoAhead.bin，如圖5.1所示。完整的程序鏡像大小為3340Bytes

　　當前在節(jié)點上已經(jīng)運行了Led.bin,我們將使用Led.bin和GoAhead.bin進行比較，生成patch.bin文件，即補丁文件。

　　我們看到，生成的patch.bin文件僅僅是原程序GoAhead.bin的1/3大小!圖5.3是patch.bin代表的命令(截取一部分)。

　　下面從GoAhead.bin 生成 RandomWalk.bin，RandomWalk.bin的大小如圖5.4所示：

　　圖5.5從生成的patch.bin文件的大小可以看到，其為RandomWalk的大約1/3。但有個值得注意的地方是，RandomWalk.bin比GoAhead.bin大了1000多個字節(jié)。添加的著1000多個字節(jié)是占patch.bin的主要內(nèi)容?？梢姲l(fā)送patch.bin比較適合于修改部分變量或者函數(shù)的時候。如果是單純的增加功能，比較適合于發(fā)送完整的鏡像文件。

　　五 總結(jié)

　　測試結(jié)果表明，本設計實現(xiàn)了可靠性無線批量嵌入式節(jié)點程序更新，燒錄出錯率低;更新效率高;不依賴操作系統(tǒng)，具有很好的可移植性，項目總體上實現(xiàn)了設計的目標。另一方面由于時間限制，系統(tǒng)仍然存在一些不足。以下是設計中幾點需要優(yōu)化的地方和相應的改進意見。

　　系統(tǒng)在Linux環(huán)境下進行了開發(fā)和應用，沒有開發(fā)Windows版本。項目組準備在下一階段把系統(tǒng)移植到Windows平臺上。

　　尚未實現(xiàn)程序的動態(tài)更新，即每次更新前都要將正在運行的程序關掉，強制節(jié)點進入準備狀態(tài)?？梢苑峙湟粋€專用線程用于程序更新，同時為了避免更新對正在運行的程序造成影響，需要在更新過程中引入動態(tài)鏈接技術