嵌入式多節(jié)點的無線批量程序更新系統(tǒng)設(shè)計(一)

　　一 總體設(shè)計和平臺簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　為此我們定義了一系列基本的更新操作命令，以及兩個輔助的索引指針：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來替換，并且in_index和out_index分別加1。

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

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

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

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

　　2.1 命令的表示

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

　　有幾個需要注意的地方：

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

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

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

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

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

表3.1

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

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

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

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

　　2.2 命令的產(chǎn)生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　整體的流程為:

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

　　3.1 Deluge協(xié)議簡介

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

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

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