嵌入式多節點(diǎn)的無(wú)線(xiàn)批量程序更新系統設計(一)

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

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

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

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

　　2.2 命令的產(chǎn)生

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

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

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

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

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

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

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

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

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

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

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

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

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

　　代碼3.2生成最小代價(jià)的操作序列

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

　　2.3在LM3S1968上的實(shí)現

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

　　整體的流程為:

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

　　3.1 Deluge協(xié)議簡(jiǎn)介

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

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

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