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

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

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

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

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

　　2.2 命令的產(chǎn)生

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

　　假設(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ù)，別且記錄下其操作，我們就能得到最小的補(bǔ)丁文件。這樣我們有以下幾種情況：

　　如果最后的操作為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生成最小代價的操作序列

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

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

　　在PC機(jī)上的部分比較容易實(shí)現(xiàn)(生成patch文件)。但在LM3S1968這個嵌入式芯片上進(jìn)行代碼的替換就不是很簡單了。首先我們要確定各個文件的位置。這里為了簡單起見，將flash的0x0000到0x3000處，設(shè)為更新服務(wù)程序區(qū)，初始化必要的硬件(通信、flash等),等待基站發(fā)送的命令來更新程序或者直接將控制轉(zhuǎn)移給應(yīng)用程序程序，本部分的程序在啟動后首先運(yùn)行。如果檢測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ū)，存放待運(yùn)行的程序。0x7000以后存放這從主機(jī)發(fā)來的Patch文件。

　　整體的流程為:

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

　　3.1 Deluge協(xié)議簡介

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

　　在Deluge協(xié)議中，采用了協(xié)商式交互策略(ADV-REQ-DATA)來實(shí)現(xiàn)受控泛洪。而整個網(wǎng)絡(luò)由狀態(tài)機(jī)來控制數(shù)據(jù)的分發(fā)，網(wǎng)絡(luò)中每個節(jié)點(diǎn)都處在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ù)乃俣龋趨f(xié)議中的具體實(shí)現(xiàn)是流水線傳輸(Pipelining)。

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