一 總體設計和平臺簡介

項目旨在實現多ARM節點通過無線通信完成對批量節點的程序燒錄，如圖2.1所示。系統分為上位機、發射接收模塊和待燒錄節點三個部分，上位機通過ID號選擇待燒錄節點并通過無線模塊向下廣播燒錄數據，各被選擇節點通過無線模塊接收燒錄數據檢查無誤后存儲。上位機軟件設定待燒錄節點的ID、燒錄文件目錄、發送數據包大小、發送速率等參數后將數據打包傳送到基站，基站通過無線發射模塊廣播數據。

圖2.1 多節點無線批量燒錄示意

整體思想是利用已有的代碼和目標代碼進行比較。將兩者的差異通過無線網絡(802.15.4)廣播出去。在每個接受節點根據收到的差異文件(也就是補丁文件patch)，對原有代碼進行修改(patching的過程)以達到更新程序的目的。

總體上來說本項目有兩大難點，涉及到巧妙的算法設計。

1、如何用盡可能少的字節數，來表示不同代碼之間的差異？

2、如何確保可靠性傳輸？

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

1、使用盡可能小的RAM。因為嵌入式芯片的RAM普遍珍貴。

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

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

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

圖2.2 硬件平臺eMouse

項目開發系統環境為Ubuntu9.04，程序編譯和下載工具分別為開源的sourcery G++和Openocd，用戶界面采用java語言編寫。

以下章節將對系統設計作詳盡的論述。

二 程序更新設計與實現

一些傳統的更新方法注重代碼本身的特點。比如以函數為基本的更新單位。在每個節點上運行一個動態鏈接器，將新的函數重新鏈接到原程序。其實代碼本身可以將其視為一串二進制的文本文件。代碼的更新即是從一串舊的文本更新為一串新的文本。

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

基本的命令如下：

Copy:將in_index所指的字節復制到out_index處，并且in_index和out_index分別加1。

Replace A:將當前out_index所指的字節用A來替換，并且in_index和out_index分別加1。

Delete:in_index加1,out_index不變。實際為刪除in_index所指的字節

Insert A:在當前out_index處插入A，in_index不變,out_index加1。

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

其中包含了如下的子問題：

2.1 命令的表示

通過上面所說的基本命令的組合，我們可以表示出從一個舊文件到一個新文件的過程。隨之帶來了一個問題。這些命令應該如何表示才能盡可能的降低補丁文件(命令的組合)的大小？

有幾個需要注意的地方：

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

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

如果可以利用Replace命令，就不要用Delete和Insert命令的組合。這其實是另一重要的子問題:如何根據這些命令產生盡可能少補丁文件？

有五條基本命令，這樣為了區別這五條命令，至少需要3個比特。

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

表3.1

經過大量實驗，我們發現連續出現Copy的情況最多，因此Copy命令操作碼只有1位，即只要是最左端比特為1，則此命令為Copy命令。這樣Copy的操作數為15個比特，一次能表示復制32768個字節。同理，Delete的格式同Copy時相同的，只不過其操作碼較長，操作數只有13位，最多能代表刪除8192個字節。實際上這也完全夠用了。

Replace和Insert操作碼的有效位為最左端三位，緊跟著5個比特是保留位，當前還沒有用到。操作數的長度為一個字節，表示當前要替換的或者要插入的新值。

Kill命令操作碼為左端3個比特，剩下的15個比特都是保留位。操作數的長度為一個字節，表示刪除的起始索引。

綜上可以看出，指令的格式都是定長的——2個字節。定長的代價是會浪費一定的比特。造成實際生成的補丁文件略大(由于Insert，Replace和Kill的保留位)。但正如MIPS處理器，定長的規定使得整個指令集簡潔有序。雖然產生的指令條數要比X86系列的CISC機要多，但簡潔的特性總是讓人喜歡的。

2.2 命令的產生

這是最有挑戰性的問題，如何根據前面定義的基本命令，產生盡可能小的操作指令集(補丁文件)？仔細觀察發現，其實此問題包含了一個最優子結構，也就是說，我們可以用動態規劃的算法來解決這個問題，保證產生的補丁文件是最小的。

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

1. 如果最后的操作為Copy，則一定有x[i] = y[j]。原問題包含將X_i-1 轉化到Y_j-1的子問題。c[i,j] = c[i-1,j-1]+1

2. 如果最后的操作為Replace，則一定有x[i] != y[j]。原問題包含將X_i-1 轉化到Y_j-1的子問題。c[i,j] = c[i-1,j-1]+1

3. 如果最后的操作為 Delete，則沒有什么必須滿足的條件。原問題包含將X_i-1 轉化到Y_j的子問題。c[i,j] = c[i-1,j]+1

4. 如果最后的操作為 Insert，也沒有什么必須滿足的條件。原問題包含將X_i 轉化到Y_j-1的子問題。c[i,j] = c[i,j-1]+1

5. 如果最后的操作為Kill。由于Kill表示刪除源程序所有剩余的字節。Kill只能出現在最后一個操作上。即完成Kill后就已經使得X_m 轉化為了Y_n。

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

這樣所有的情況都已經包含在內。對于每一個i,j我們可以求得最c[i,j]

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

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

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

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

代碼3.2生成最小代價的操作序列

這樣，我們得到在定長命令下，最小的補丁文件。以上都是在PC機上進行的。即界面中的生成補丁按鈕。

圖3.3 界面-生成補丁功能

2.3在LM3S1968上的實現

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

整體的流程為:

圖3.4更新流程圖

三 可靠數據分發協議的設計與實現

3.1 Deluge協議簡介

Deluge協議是一個優秀的可靠性數據分發協議，由加利福尼亞大學伯克利分校的David Culler等人在2004年提出的，首先在TinyOS1.1.8操作系統上實現。協議的設計初衷是用來進行較大規模的數據分發，比如大塊數據傳輸和遠程系統升級等。

在Deluge協議中，采用了協商式交互策略（ADV-REQ-DATA）來實現受控泛洪。而整個網絡由狀態機來控制數據的分發，網絡中每個節點都處在MAINTAIN、RX和TX三種狀態的其中一種，并且遵循該種狀態下的一系列動作規則。在Deluge協議中，把將要分發的目標文件(Sobj)劃分為固定大小的程序包(Spkt)，由N個程序包(Spkt)組成一個程序頁(Spage)。Deluge協議對整個目標文件數據的劃分如圖4.1所示。基于這種數據結構，Deluge協議支持空間多路技術以提高數據傳輸的速度，在協議中的具體實現是流水線傳輸（Pipelining）。

圖4.1 Deluge協議中分發數據的結構

Deluge協議引入了復雜的控制信息，而目前很多無線傳感器網絡應用中的節點都不能支持像TinyOS這樣的操作系統，因此實現起來難度較高；同時，許多數據分發的應用場景提供Deluge協議中的一些高級功能并不能明顯提升網絡性能，比如網絡節點較少則不需要流水線數據分發，數據塊較少則不需要分頁機制等。基于以上原因，本設計在提出若干常見應用場景假設的基礎上對Deluge協議做了簡化和補充。

3.2 可靠數據分發協議的設計

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

假設一：網絡節點不支持高級的操作系統。可以理解為必須考慮節點處理和通信能力有限，而且通信協議要從底層（如MAC層）實現。

假設二：大部分待燒錄節點分布在數據基站的通訊范圍之內。可以理解為通信協議不需要實現復雜的多跳通信和流水線，可以充分利用數據基站第一次數據廣播，這一點下文會詳細闡述。

基于以上兩點假設，可靠性數據分發協議的具體設計如下。

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

圖4.2 數據分發兩階段通信方式示意圖

（實線代表發送完整數據文件，虛線表示發送數據頁）

1、第一輪發送階段。

數據基站（如PC）在接收節點準備好后不間斷廣播數據幀，直至數據發送結束；接收節點盡力接收數據，并記錄自己已有數據幀的id信息，期間不向源節點發送反饋信息。

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

1. 節點間交流階段。

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

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

節點首先廣播廣告，每一個廣告包含一個摘要(φ)，摘要(φ)由兩部分組成：(1)本節點的IP標識v。(2)本節點的最大可用頁號p，即φ(v,p)。可用頁號p的定義：頁p所包含的包被節點全部接收，稱頁p完成。頁p被完成并且它之前的所有的頁(0,p)也被節點全部接收，稱頁p可用。節點通過廣告來了解對方擁有的數據信息，繼而向比自己數據更完備的節點發送數據頁請求。協議中將時間分成時間片(round)，在每一個時間片中，節點來決定是否廣播一個廣告。假設時間片的長度由T_m,i來表示，它的上下界由T_l和T_h來表示，則有取T_lT_m,iT_h。在每一個時間片i中，節點維護—個隨機值r_i，r_i的值在T_m,i/2和T_m,i之間，r_i值的范圍選取是為了解決短監聽問題(short—listen problem)。

交流階段中，節點擁有“維護”、“請求”和“發送”中的人一個狀態。節點在“維護”狀態廣播廣告并聽取其他節點的廣播；在請求階段向其他節點發送數據頁請求，并接收對方發來的數據；在發送狀態廣播被請求的數據頁。圖4.3為狀態轉換示意圖。主要的交流規則如下。

（1）“維護”狀態規則

M1: 假設時間片i的開始時間為t_i，節點在t_i+r_i的時間段內，若接收不到廣告φ=φ，則廣播廣告φ；若收到與φ不一致的廣告（包括φ=φ、廣告幀和數據幀等），則調整時間片為T_l，并立即重新開始時間片；若接收到廣告φ=φ，則調整時間片為min(2*T_m,i ,T_h )。

M2: 節點在收到廣告φ(v,p)中p大于自身的最大可用頁p時，轉向“請求”狀態，向節點v發送數據頁請求；節點收到請求幀，則轉向“發送”狀態，廣播被請求數據頁。

規則1能控制冗余廣告的發送，節約網絡資源，并且根據網絡狀況動態調整時間片長度，從而是網絡資源得到有效的利用。

規則2實現從“維護”狀態到“請求”和“發送”狀態的轉換。

（2）“請求”狀態規則：

M3：若節點在向源節點發出數據頁請求后節點在時間t（t為自定義時間長度，是經驗值，根據網絡狀況而定）內沒有收到數據，則再次發送請求，若累計請求次數大于k（k為自定義次數），則認為請求失敗，返回“維護”狀態；若節點接收到數據頁，則在接收結束后返回“維護”狀態。

規則3中考慮到網絡的質量因素，定義了等待時間t和最大請求次數k。

（3）“發送”狀態規則：

M4：節點進入“發送”狀態立即廣播被請求的數據頁，廣播結束后返回“維護”狀態。

規則4中要注意的是，節點以廣播的方式發送數據，這意味著處于“請求”狀態的節點可以接收任何節點（不一定是它請求的指定節點）發送的符合其需要的數據包，這也是協議中避免網絡冗余的一個體現。

圖4.3 可靠數據分發交流階段節點狀態轉換示意圖

以上是本設計中可靠數據分發協議的全部內容，本文在下一節中將詳細論述協議的軟件設計實現。

3.3 可靠數據分發協議的軟件設計實現

協議的軟件設計在網絡層實現，涉及到MAC層接口的調用。本節先簡單介紹本設計實驗平臺上網絡模塊提供的MAC層應用接口，然后詳細論述軟件的設計和實現。

3.3.1 MAC層接口簡介

首先做兩點說明。

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

第二，網絡層只使用了MAC層提供的數據幀發送和數據幀接收兩個接口，網絡層的幀結構包含在MAC數據幀的數據域中。

從第一點可以看到，協議在網絡層實現可靠數據傳輸的機制，降低了對MAC層通信質量的要求，而第二點說明協議僅僅需要MAC層提供兩個最基本的應用接口。本設計中的可靠數據分發協議對底層通信的要求很低，具有較好的魯棒性和可移植性。

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

圖4.4 MAC層接口數據幀發送命令

3.3.2 可靠數據分發協議的數據結構設計

網絡層數據要經過緩存，解析再到存儲或者執行三步操作，并且不同種類的幀要區別處理，因此一個好的數據結構設計方案對簡化數據處理操作和提高數據處理效率是非常有必要的。圖4.5為網絡層數據流圖，數據幀的流向為：

1. 從MAC層讀入后放入原始數據緩沖區；

2. 經解析后得到幀結構；

3. 將幀結構作相關處理后僅提取頁號（p）、幀號（id）和數據（data）放到寫flash緩沖區；

4. 寫flash。

注意以上是數據幀的流向，除數據幀以外的其他類型幀（如請求幀，結束幀等）只執行第（1）、（2）步操作。下面著重論述圖中每個階段涉及到的數據結構。

圖4.5 網絡層數據流圖

1. 緩沖區Deluge_buf

Deluge_buf是一個環形緩沖區，用于緩存原始的網絡層數據。緩沖區實際上是由一個環形鏈表、兩個指針和一個整數組成。鏈表的每個節點用于存儲實際數據，節點數目根據需要而定；一個tail指針和一個head指針，分別指鏈表的讀出點和寫入點，執行一次讀出或寫入操作后，tail或head指針都向前移動一次，整數的作用是統計當前鏈表上可用節點的數目。Deluge_buf結構體定義如下：

struct Deluge_buf {

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

uint8 recv_num;

uint8 queue_head;

uint8 queue_tail;

};

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

1. 幀結構DelugeData

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

表4.1 DelugeData中數據項含義的定義

3、緩沖區Flash_buf

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

3.3.3 可靠數據分發協議的軟件架構設計

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

第一階段：

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

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

第二階段：

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

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

四 系統測試

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

Led.bin實現簡單的跑馬燈；

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

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

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

圖5.1 GoAhead.bin的大小

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

圖5.2生成的patch.bin文件

我們看到，生成的patch.bin文件僅僅是原程序GoAhead.bin的1/3大小！圖5.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。但有個值得注意的地方是，RandomWalk.bin比GoAhead.bin大了1000多個字節。添加的著1000多個字節是占patch.bin的主要內容。可見發送patch.bin比較適合于修改部分變量或者函數的時候。如果是單純的增加功能，比較適合于發送完整的鏡像文件。

圖5.5 patch.bin文件

五 總結

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

1. 系統在Linux環境下進行了開發和應用，沒有開發Windows版本。項目組準備在下一階段把系統移植到Windows平臺上。

2. 尚未實現程序的動態更新，即每次更新前都要將正在運行的程序關掉，強制節點進入準備狀態。可以分配一個專用線程用于程序更新，同時為了避免更新對正在運行的程序造成影響，需要在更新過程中引入動態鏈接技術