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

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

　　整體思想是利用已有的代碼和目標(biāo)代碼進(jìn)行比較。將兩者的差異通過(guò)無(wú)線(xiàn)網(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))之外，還有一些別的附加要求。如果滿(mǎn)足了能夠提高系統(tǒng)的持久性。分別是：

　　1、使用盡可能小的RAM。因?yàn)榍度胧叫酒腞AM普遍珍貴。

　　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ù)管理的塊保護(hù)和數(shù)據(jù)編程;板上Zigbee模塊通過(guò)串口與CPU通信，模塊僅提供MAC層服務(wù)，CPU與模塊間以MAC幀的形式通過(guò)串口傳遞數(shù)據(jù)。eMouse外觀(guān)如圖2.2所示。

　　項(xiàng)目開(kāi)發(fā)系統(tǒng)環(huán)境為Ubuntu9.04，程序編譯和下載工具分別為開(kāi)源的sourcery G++和Openocd，用戶(hù)界面采用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ì)觀(guān)察發(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]，Yj = y[1..j]，其中x[1..i]表示源程序的第一個(gè)到第i個(gè)字節(jié)，y[1..j]表示目標(biāo)程序的第一個(gè)到第j字節(jié)。用c[i,j]表示從Xi 到Y(jié)j所用的最小的代價(jià)。由于所有的命令長(zhǎng)度均相同，故每條命令代價(jià)都為1，c[i,j]也就是代表從Xi 到Y(jié)j 所需的最小的命令數(shù)，求得最小的命令數(shù)，別且記錄下其操作，我們就能得到最小的補(bǔ)丁文件。這樣我們有以下幾種情況：

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

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

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

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

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

　　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ǔ)丁按鈕。

　　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文件。

　　整體的流程為:

　　三 可靠數(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)是流水線(xiàn)傳輸(Pipelining)。

　　Deluge協(xié)議引入了復(fù)雜的控制信息，而目前很多無(wú)線(xiàn)傳感器網(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)較少則不需要流水線(xiàn)數(shù)據(jù)分發(fā)，數(shù)據(jù)塊較少則不需要分頁(yè)機(jī)制等。基于以上原因，本設(shè)計(jì)在提出若干常見(jiàn)應(yīng)用場(chǎng)景假設(shè)的基礎(chǔ)上對(duì)Deluge協(xié)議做了簡(jiǎn)化和補(bǔ)充。