經(jīng)過大量實(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í)相同的，只不過其操作碼較長(zhǎng)，操作數(shù)只有13位，最多能代表刪除8192個(gè)字節(jié)。實(shí)際上這也完全夠用了。

　　Replace和Insert操作碼的有效位為最左端三位，緊跟著5個(gè)比特是保留位，當(dāng)前還沒有用到。操作數(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)性的問題，如何根據(jù)前面定義的基本命令，產(chǎn)生盡可能小的操作指令集(補(bǔ)丁文件)?仔細(xì)觀察發(fā)現(xiàn)，其實(shí)此問題包含了一個(gè)最優(yōu)子結(jié)構(gòu)，也就是說，我們可以用動(dòng)態(tài)規(guī)劃的算法來解決這個(gè)問題，保證產(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]。原問題包含將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)在最后一個(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)單起見，將flash的0x0000到0x3000處，設(shè)為更新服務(wù)程序區(qū)，初始化必要的硬件(通信、flash等),等待基站發(fā)送的命令來更新程序或者直接將控制轉(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ā)來的其他命令。需要注意的是在將控制權(quán)轉(zhuǎn)移到應(yīng)用程序時(shí)，中斷向量表的位置，棧指針，是兩個(gè)要小心設(shè)置的量。否則會(huì)造成整個(gè)系統(tǒng)的崩潰。而且本部分只能用匯編語(yǔ)言寫，具體可以參見bl_start_gcc.S。0x3000到0x7000處為應(yīng)用程序區(qū)，存放待運(yùn)行的程序。0x7000以后存放這從主機(jī)發(fā)來的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ì)初衷是用來進(jìn)行較大規(guī)模的數(shù)據(jù)分發(fā)，比如大塊數(shù)據(jù)傳輸和遠(yuǎn)程系統(tǒng)升級(jí)等。

　　在Deluge協(xié)議中，采用了協(xié)商式交互策略(ADV-REQ-DATA)來實(shí)現(xiàn)受控泛洪。而整個(gè)網(wǎng)絡(luò)由狀態(tài)機(jī)來控制數(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)。

　　Deluge協(xié)議引入了復(fù)雜的控制信息，而目前很多無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中的節(jié)點(diǎn)都不能支持像TinyOS這樣的操作系統(tǒng)，因此實(shí)現(xiàn)起來難度較高;同時(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ī)制等?；谝陨显颍驹O(shè)計(jì)在提出若干常見應(yīng)用場(chǎng)景假設(shè)的基礎(chǔ)上對(duì)Deluge協(xié)議做了簡(jiǎn)化和補(bǔ)充。