嵌入式多節(jié)點(diǎn)的無(wú)線批量程序更新系統(tǒng)設(shè)計(jì)

一 總體設(shè)計(jì)和平臺(tái)簡(jiǎn)介

項(xiàng)目旨在實(shí)現(xiàn)多ARM節(jié)點(diǎn)通過(guò)無(wú)線通信完成對(duì)批量節(jié)點(diǎn)的程序燒錄，如圖2.1所示。系統(tǒng)分為上位機(jī)、發(fā)射接收模塊和待燒錄節(jié)點(diǎn)三個(gè)部分，上位機(jī)通過(guò)ID號(hào)選擇待燒錄節(jié)點(diǎn)并通過(guò)無(wú)線模塊向下廣播燒錄數(shù)據(jù)，各被選擇節(jié)點(diǎn)通過(guò)無(wú)線模塊接收燒錄數(shù)據(jù)檢查無(wú)誤后存儲(chǔ)。上位機(jī)軟件設(shè)定待燒錄節(jié)點(diǎn)的ID、燒錄文件目錄、發(fā)送數(shù)據(jù)包大小、發(fā)送速率等參數(shù)后將數(shù)據(jù)打包傳送到基站，基站通過(guò)無(wú)線發(fā)射模塊廣播數(shù)據(jù)。

圖2.1 多節(jié)點(diǎn)無(wú)線批量燒錄示意

整體思想是利用已有的代碼和目標(biāo)代碼進(jìn)行比較。將兩者的差異通過(guò)無(wú)線網(wǎng)絡(luò)(802.15.4)廣播出去。在每個(gè)接受節(jié)點(diǎn)根據(jù)收到的差異文件(也就是補(bǔ)丁文件patch)，對(duì)原有代碼進(jìn)行修改(patching的過(guò)程)以達(dá)到更新程序的目的。

總體上來(lái)說(shuō)本項(xiàng)目有兩大難點(diǎn)，涉及到巧妙的算法設(shè)計(jì)。

1、如何用盡可能少的字節(jié)數(shù)，來(lái)表示不同代碼之間的差異？

2、如何確?？煽啃詡鬏?？

關(guān)于問(wèn)題1，我們知道要待傳輸?shù)淖止?jié)數(shù)越少，對(duì)通信的要求越低。更新程序的效率也會(huì)更高。而且少的字節(jié)數(shù)也意味著丟更少的包。關(guān)于問(wèn)題2，由于我們是要對(duì)代碼進(jìn)行修正，所以一個(gè)字節(jié)的錯(cuò)誤可能就會(huì)造成整個(gè)程序的崩潰。這對(duì)嵌入式程序，特別是運(yùn)行在成千上萬(wàn)個(gè)節(jié)點(diǎn)上的程序是不可接受的，必須保證100%的正確接受。除此兩大難點(diǎn)（也是關(guān)鍵點(diǎn)）之外，還有一些別的附加要求。如果滿足了能夠提高系統(tǒng)的持久性。分別是：

1、使用盡可能小的RAM。因?yàn)?a class="contentlabel" href="http://butianyuan.cn/news/listbylabel/label/嵌入式">嵌入式芯片的RAM普遍珍貴。

2、消耗盡可能少的能量。

3、更新速度盡可能的快。

項(xiàng)目使用的硬件平臺(tái)是我們自制的智能小車(chē)eMouse 。平臺(tái)采用 TI公司32位Stellaris LM3S1968微處理器，工作頻率為50MHz，內(nèi)含256 KB單周期Flash和64 KB單周期SRAM，flash支持可由用戶管理的塊保護(hù)和數(shù)據(jù)編程；板上Zigbee模塊通過(guò)串口與CPU通信，模塊僅提供MAC層服務(wù)，CPU與模塊間以MAC幀的形式通過(guò)串口傳遞數(shù)據(jù)。eMouse外觀如圖2.2所示。

圖2.2 硬件平臺(tái)eMouse

項(xiàng)目開(kāi)發(fā)系統(tǒng)環(huán)境為Ubuntu9.04，程序編譯和下載工具分別為開(kāi)源的sourcery G++和Openocd，用戶界面采用java語(yǔ)言編寫(xiě)。

以下章節(jié)將對(duì)系統(tǒng)設(shè)計(jì)作詳盡的論述。

二 程序更新設(shè)計(jì)與實(shí)現(xiàn)

一些傳統(tǒng)的更新方法注重代碼本身的特點(diǎn)。比如以函數(shù)為基本的更新單位。在每個(gè)節(jié)點(diǎn)上運(yùn)行一個(gè)動(dòng)態(tài)鏈接器，將新的函數(shù)重新鏈接到原程序。其實(shí)代碼本身可以將其視為一串二進(jìn)制的文本文件。代碼的更新即是從一串舊的文本更新為一串新的文本。

為此我們定義了一系列基本的更新操作命令，以及兩個(gè)輔助的索引指針：in_index以及out_index。in_index代表輸入文件當(dāng)前的索引值，而out_index代表輸出文件當(dāng)前的索引值。

基本的命令如下：

Copy:將in_index所指的字節(jié)復(fù)制到out_index處，并且in_index和out_index分別加1。

Replace A:將當(dāng)前out_index所指的字節(jié)用A來(lái)替換，并且in_index和out_index分別加1。

Delete:in_index加1,out_index不變。實(shí)際為刪除in_index所指的字節(jié)

Insert A:在當(dāng)前out_index處插入A，in_index不變,out_index加1。

Kill:表示刪除in_index后所有的原程序代碼。

其中包含了如下的子問(wèn)題：

2.1 命令的表示

通過(guò)上面所說(shuō)的基本命令的組合，我們可以表示出從一個(gè)舊文件到一個(gè)新文件的過(guò)程。隨之帶來(lái)了一個(gè)問(wèn)題。這些命令應(yīng)該如何表示才能盡可能的降低補(bǔ)丁文件(命令的組合)的大小？

有幾個(gè)需要注意的地方：

如果有連續(xù)的Copy命令，我們可以將其合并成一條命令，只要在Copy后加上表示長(zhǎng)度的Length參數(shù)即可。

同理，如果有連續(xù)的Delete命令，也可以將其合并成一條命令，只要在Delete后加上表示長(zhǎng)度的Length參數(shù)即可。

如果可以利用Replace命令，就不要用Delete和Insert命令的組合。這其實(shí)是另一重要的子問(wèn)題:如何根據(jù)這些命令產(chǎn)生盡可能少補(bǔ)丁文件？

有五條基本命令，這樣為了區(qū)別這五條命令，至少需要3個(gè)比特。

由于大多數(shù)情況下，更新的大多數(shù)是程序的參數(shù)。也就是說(shuō)Copy命令的數(shù)目遠(yuǎn)遠(yuǎn)大于其他命令。我們定義這5條命令如下表所示：

表3.1

經(jīng)過(guò)大量實(shí)驗(yàn)，我們發(fā)現(xiàn)連續(xù)出現(xiàn)Copy的情況最多，因此Copy命令操作碼只有1位，即只要是最左端比特為1，則此命令為Copy命令。這樣Copy的操作數(shù)為15個(gè)比特，一次能表示復(fù)制32768個(gè)字節(jié)。同理，Delete的格式同Copy時(shí)相同的，只不過(guò)其操作碼較長(zhǎng)，操作數(shù)只有13位，最多能代表刪除8192個(gè)字節(jié)。實(shí)際上這也完全夠用了。

Replace和Insert操作碼的有效位為最左端三位，緊跟著5個(gè)比特是保留位，當(dāng)前還沒(méi)有用到。操作數(shù)的長(zhǎng)度為一個(gè)字節(jié)，表示當(dāng)前要替換的或者要插入的新值。

Kill命令操作碼為左端3個(gè)比特，剩下的15個(gè)比特都是保留位。操作數(shù)的長(zhǎng)度為一個(gè)字節(jié)，表示刪除的起始索引。

綜上可以看出，指令的格式都是定長(zhǎng)的——2個(gè)字節(jié)。定長(zhǎng)的代價(jià)是會(huì)浪費(fèi)一定的比特。造成實(shí)際生成的補(bǔ)丁文件略大(由于Insert，Replace和Kill的保留位)。但正如MIPS處理器，定長(zhǎng)的規(guī)定使得整個(gè)指令集簡(jiǎn)潔有序。雖然產(chǎn)生的指令條數(shù)要比X86系列的CISC機(jī)要多，但簡(jiǎn)潔的特性總是讓人喜歡的。

2.2 命令的產(chǎn)生

這是最有挑戰(zhàn)性的問(wèn)題，如何根據(jù)前面定義的基本命令，產(chǎn)生盡可能小的操作指令集(補(bǔ)丁文件)？仔細(xì)觀察發(fā)現(xiàn)，其實(shí)此問(wèn)題包含了一個(gè)最優(yōu)子結(jié)構(gòu)，也就是說(shuō)，我們可以用動(dòng)態(tài)規(guī)劃的算法來(lái)解決這個(gè)問(wèn)題，保證產(chǎn)生的補(bǔ)丁文件是最小的。

假設(shè)原程序的長(zhǎng)度為m個(gè)字節(jié)，目標(biāo)程序的長(zhǎng)度為n個(gè)字節(jié)。定義= x[1..i]，Y_j = y[1..j]，其中x[1..i]表示源程序的第一個(gè)到第i個(gè)字節(jié)，y[1..j]表示目標(biāo)程序的第一個(gè)到第j字節(jié)。用c[i,j]表示從X_i 到Y(jié)_j所用的最小的代價(jià)。由于所有的命令長(zhǎng)度均相同，故每條命令代價(jià)都為1，c[i,j]也就是代表從X_i 到Y(jié)_j 所需的最小的命令數(shù)，求得最小的命令數(shù)，別且記錄下其操作，我們就能得到最小的補(bǔ)丁文件。這樣我們有以下幾種情況：

1. 如果最后的操作為Copy，則一定有x[i] = y[j]。原問(wèn)題包含將X_i-1 轉(zhuǎn)化到Y(jié)_j-1的子問(wèn)題。c[i,j] = c[i-1,j-1]+1

2. 如果最后的操作為Replace，則一定有x[i] != y[j]。原問(wèn)題包含將X_i-1 轉(zhuǎn)化到Y(jié)_j-1的子問(wèn)題。c[i,j] = c[i-1,j-1]+1

3. 如果最后的操作為 Delete，則沒(méi)有什么必須滿足的條件。原問(wèn)題包含將X_i-1 轉(zhuǎn)化到Y(jié)_j的子問(wèn)題。c[i,j] = c[i-1,j]+1

4. 如果最后的操作為 Insert，也沒(méi)有什么必須滿足的條件。原問(wèn)題包含將X_i 轉(zhuǎn)化到Y(jié)_j-1的子問(wèn)題。c[i,j] = c[i,j-1]+1

5. 如果最后的操作為Kill。由于Kill表示刪除源程序所有剩余的字節(jié)。Kill只能出現(xiàn)在最后一個(gè)操作上。即完成Kill后就已經(jīng)使得X_m 轉(zhuǎn)化為了Y_n。

c[m,n] = min(c[i,n]) + 1, 0= i= m

這樣所有的情況都已經(jīng)包含在內(nèi)。對(duì)于每一個(gè)i,j我們可以求得最c[i,j]

公式從上到下依次代表了Copy,Replace,Delete,Insert和Kill這五種情況。

整體的偽代碼如代碼3.1所示：注意，我們不僅求得每一個(gè)c[i,j]而且記錄下了與其相應(yīng)的操作.op[i,j]這個(gè)數(shù)組中的每個(gè)元素為一個(gè)結(jié)構(gòu)體，包含操作數(shù)以及操作碼。

代碼3.1得到c[i,j]以及op[i,j]

這樣，我們得到了c[m,n]以及操作表。下面就是要求得操作序列。根據(jù)之前生成的操作表，采用一個(gè)遞歸的方法得出最小代價(jià)的操作序列。偽代碼如代碼3.2所示：

代碼3.2生成最小代價(jià)的操作序列

這樣，我們得到在定長(zhǎng)命令下，最小的補(bǔ)丁文件。以上都是在PC機(jī)上進(jìn)行的。即界面中的生成補(bǔ)丁按鈕。

圖3.3 界面-生成補(bǔ)丁功能

2.3在LM3S1968上的實(shí)現(xiàn)

在PC機(jī)上的部分比較容易實(shí)現(xiàn)(生成patch文件)。但在LM3S1968這個(gè)嵌入式芯片上進(jìn)行代碼的替換就不是很簡(jiǎn)單了。首先我們要確定各個(gè)文件的位置。這里為了簡(jiǎn)單起見(jiàn)，將flash的0x0000到0x3000處，設(shè)為更新服務(wù)程序區(qū)，初始化必要的硬件(通信、flash等),等待基站發(fā)送的命令來(lái)更新程序或者直接將控制轉(zhuǎn)移給應(yīng)用程序程序，本部分的程序在啟動(dòng)后首先運(yùn)行。如果檢測(cè)0x4000處為合法的應(yīng)用程序，則將控制權(quán)轉(zhuǎn)交給它，每個(gè)應(yīng)用程序在接受到了“等待接受”命令后，又將控制權(quán)轉(zhuǎn)移給更新服務(wù)程序，等待從基站發(fā)來(lái)的其他命令。需要注意的是在將控制權(quán)轉(zhuǎn)移到應(yīng)用程序時(shí)，中斷向量表的位置，棧指針，是兩個(gè)要小心設(shè)置的量。否則會(huì)造成整個(gè)系統(tǒng)的崩潰。而且本部分只能用匯編語(yǔ)言寫(xiě)，具體可以參見(jiàn)bl_start_gcc.S。0x3000到0x7000處為應(yīng)用程序區(qū)，存放待運(yùn)行的程序。0x7000以后存放這從主機(jī)發(fā)來(lái)的Patch文件。

整體的流程為:

圖3.4更新流程圖

三 可靠數(shù)據(jù)分發(fā)協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)

3.1 Deluge協(xié)議簡(jiǎn)介

Deluge協(xié)議是一個(gè)優(yōu)秀的可靠性數(shù)據(jù)分發(fā)協(xié)議，由加利福尼亞大學(xué)伯克利分校的David Culler等人在2004年提出的，首先在TinyOS1.1.8操作系統(tǒng)上實(shí)現(xiàn)。協(xié)議的設(shè)計(jì)初衷是用來(lái)進(jìn)行較大規(guī)模的數(shù)據(jù)分發(fā)，比如大塊數(shù)據(jù)傳輸和遠(yuǎn)程系統(tǒng)升級(jí)等。

在Deluge協(xié)議中，采用了協(xié)商式交互策略（ADV-REQ-DATA）來(lái)實(shí)現(xiàn)受控泛洪。而整個(gè)網(wǎng)絡(luò)由狀態(tài)機(jī)來(lái)控制數(shù)據(jù)的分發(fā)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都處在MAINTAIN、RX和TX三種狀態(tài)的其中一種，并且遵循該種狀態(tài)下的一系列動(dòng)作規(guī)則。在Deluge協(xié)議中，把將要分發(fā)的目標(biāo)文件(Sobj)劃分為固定大小的程序包(Spkt)，由N個(gè)程序包(Spkt)組成一個(gè)程序頁(yè)(Spage)。Deluge協(xié)議對(duì)整個(gè)目標(biāo)文件數(shù)據(jù)的劃分如圖4.1所示?；谶@種數(shù)據(jù)結(jié)構(gòu)，Deluge協(xié)議支持空間多路技術(shù)以提高數(shù)據(jù)傳輸?shù)乃俣?，在協(xié)議中的具體實(shí)現(xiàn)是流水線傳輸（Pipelining）。

圖4.1 Deluge協(xié)議中分發(fā)數(shù)據(jù)的結(jié)構(gòu)

Deluge協(xié)議引入了復(fù)雜的控制信息，而目前很多無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中的節(jié)點(diǎn)都不能支持像TinyOS這樣的操作系統(tǒng)，因此實(shí)現(xiàn)起來(lái)難度較高；同時(shí)，許多數(shù)據(jù)分發(fā)的應(yīng)用場(chǎng)景提供Deluge協(xié)議中的一些高級(jí)功能并不能明顯提升網(wǎng)絡(luò)性能，比如網(wǎng)絡(luò)節(jié)點(diǎn)較少則不需要流水線數(shù)據(jù)分發(fā)，數(shù)據(jù)塊較少則不需要分頁(yè)機(jī)制等。基于以上原因，本設(shè)計(jì)在提出若干常見(jiàn)應(yīng)用場(chǎng)景假設(shè)的基礎(chǔ)上對(duì)Deluge協(xié)議做了簡(jiǎn)化和補(bǔ)充。

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

在闡述具體的設(shè)計(jì)思路之前，先提出以下應(yīng)用場(chǎng)景的假設(shè)。

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

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

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

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

圖4.2 數(shù)據(jù)分發(fā)兩階段通信方式示意圖

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

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

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

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

1. 節(jié)點(diǎn)間交流階段。

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

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

節(jié)點(diǎn)首先廣播廣告，每一個(gè)廣告包含一個(gè)摘要(φ)，摘要(φ)由兩部分組成：(1)本節(jié)點(diǎn)的IP標(biāo)識(shí)v。(2)本節(jié)點(diǎn)的最大可用頁(yè)號(hào)p，即φ(v,p)?？捎庙?yè)號(hào)p的定義：頁(yè)p所包含的包被節(jié)點(diǎn)全部接收，稱(chēng)頁(yè)p完成。頁(yè)p被完成并且它之前的所有的頁(yè)(0,p)也被節(jié)點(diǎn)全部接收，稱(chēng)頁(yè)p可用。節(jié)點(diǎn)通過(guò)廣告來(lái)了解對(duì)方擁有的數(shù)據(jù)信息，繼而向比自己數(shù)據(jù)更完備的節(jié)點(diǎn)發(fā)送數(shù)據(jù)頁(yè)請(qǐng)求。協(xié)議中將時(shí)間分成時(shí)間片(round)，在每一個(gè)時(shí)間片中，節(jié)點(diǎn)來(lái)決定是否廣播一個(gè)廣告。假設(shè)時(shí)間片的長(zhǎng)度由T_m,i來(lái)表示，它的上下界由T_l和T_h來(lái)表示，則有取T_lT_m,iT_h。在每一個(gè)時(shí)間片i中，節(jié)點(diǎn)維護(hù)—個(gè)隨機(jī)值r_i，r_i的值在T_m,i/2和T_m,i之間，r_i值的范圍選取是為了解決短監(jiān)聽(tīng)問(wèn)題(short—listen problem)。

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

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

M1: 假設(shè)時(shí)間片i的開(kāi)始時(shí)間為t_i，節(jié)點(diǎn)在t_i+r_i的時(shí)間段內(nèi)，若接收不到廣告φ=φ，則廣播廣告φ；若收到與φ不一致的廣告（包括φ=φ、廣告幀和數(shù)據(jù)幀等），則調(diào)整時(shí)間片為T(mén)_l，并立即重新開(kāi)始時(shí)間片；若接收到廣告φ=φ，則調(diào)整時(shí)間片為min(2*T_m,i ,T_h )。

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

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

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

（2）“請(qǐng)求”狀態(tài)規(guī)則：

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

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

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

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

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

圖4.3 可靠數(shù)據(jù)分發(fā)交流階段節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換示意圖

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

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

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

3.3.1 MAC層接口簡(jiǎn)介

首先做兩點(diǎn)說(shuō)明。

第一，設(shè)計(jì)中使用的MAC層接口不提供絕對(duì)可靠的網(wǎng)絡(luò)通信。一方面是因?yàn)樵O(shè)計(jì)使用實(shí)驗(yàn)室自制的硬件平臺(tái)主要用于做群體實(shí)驗(yàn)，而群體實(shí)驗(yàn)不需要可靠的網(wǎng)絡(luò)通信，所以平臺(tái)的通信模塊也沒(méi)有能實(shí)現(xiàn)可靠通信的機(jī)制；另一方面要求MAC層提供可靠通信也不是必要的。

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

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

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

圖4.4 MAC層接口數(shù)據(jù)幀發(fā)送命令

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

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

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

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

3. 將幀結(jié)構(gòu)作相關(guān)處理后僅提取頁(yè)號(hào)（p）、幀號(hào)（id）和數(shù)據(jù)（data）放到寫(xiě)flash緩沖區(qū)；

4. 寫(xiě)flash。

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

圖4.5 網(wǎng)絡(luò)層數(shù)據(jù)流圖

1. 緩沖區(qū)Deluge_buf

Deluge_buf是一個(gè)環(huán)形緩沖區(qū)，用于緩存原始的網(wǎng)絡(luò)層數(shù)據(jù)。緩沖區(qū)實(shí)際上是由一個(gè)環(huán)形鏈表、兩個(gè)指針和一個(gè)整數(shù)組成。鏈表的每個(gè)節(jié)點(diǎn)用于存儲(chǔ)實(shí)際數(shù)據(jù)，節(jié)點(diǎn)數(shù)目根據(jù)需要而定；一個(gè)tail指針和一個(gè)head指針，分別指鏈表的讀出點(diǎn)和寫(xiě)入點(diǎn)，執(zhí)行一次讀出或?qū)懭氩僮骱螅瑃ail或head指針都向前移動(dòng)一次，整數(shù)的作用是統(tǒng)計(jì)當(dāng)前鏈表上可用節(jié)點(diǎn)的數(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項(xiàng)的組成在不同類(lèi)型的幀中是不同的，比如數(shù)據(jù)幀中Payload包括頁(yè)號(hào)p、幀號(hào)id和數(shù)據(jù)data以及數(shù)據(jù)長(zhǎng)度data_len，而廣告幀中只包含p和id，因此解析方法要根據(jù)type值來(lái)區(qū)分。

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

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

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

3、緩沖區(qū)Flash_buf

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

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

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

第一階段：

程序完成初始化后進(jìn)入準(zhǔn)備接收狀態(tài)，當(dāng)數(shù)據(jù)幀到來(lái)時(shí)將數(shù)據(jù)提取出來(lái)寫(xiě)到flash相應(yīng)的地址（地址由頁(yè)號(hào)p和幀號(hào)id計(jì)算得到），并將該幀標(biāo)記為“完成幀”；若接收到結(jié)束幀，則記錄結(jié)束幀的頁(yè)號(hào)p_max和幀號(hào)id_max并進(jìn)入第二階段；若接收到其他類(lèi)型幀則直接進(jìn)入第二階段。第一階段的軟件流程圖如圖4.6所示。

圖4.6 接收端軟件第一階段流程圖

第二階段：

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

圖4.7 接收端軟件第二階段流程圖

四 系統(tǒng)測(cè)試

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

Led.bin實(shí)現(xiàn)簡(jiǎn)單的跑馬燈；

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

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

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

圖5.1 GoAhead.bin的大小

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

圖5.2生成的patch.bin文件

我們看到，生成的patch.bin文件僅僅是原程序GoAhead.bin的1/3大?。D5.3是patch.bin代表的命令（截取一部分）。

圖5.3 patch.bin代表的命令

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

圖5.4 Randomalk.bin

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

圖5.5 patch.bin文件

五 總結(jié)

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

1. 系統(tǒng)在Linux環(huán)境下進(jìn)行了開(kāi)發(fā)和應(yīng)用，沒(méi)有開(kāi)發(fā)Windows版本。項(xiàng)目組準(zhǔn)備在下一階段把系統(tǒng)移植到Windows平臺(tái)上。

2. 尚未實(shí)現(xiàn)程序的動(dòng)態(tài)更新，即每次更新前都要將正在運(yùn)行的程序關(guān)掉，強(qiáng)制節(jié)點(diǎn)進(jìn)入準(zhǔn)備狀態(tài)?？梢苑峙湟粋€(gè)專(zhuān)用線程用于程序更新，同時(shí)為了避免更新對(duì)正在運(yùn)行的程序造成影響，需要在更新過(guò)程中引入動(dòng)態(tài)鏈接技術(shù)