許 宏

(淮陰工學(xué)院，江蘇淮安223003)

0 引言

隨著智能終端在各個(gè)領(lǐng)域的廣泛應(yīng)用，智能終端軟件的維護(hù)變得日益重要。因此，智能終端軟件的更新逐漸成為智能終端實(shí)際應(yīng)用的一個(gè)重要問(wèn)題。當(dāng)智能終端安裝數(shù)量較多，或安裝位置不方便的情況下，采用人工更新方式會(huì)花費(fèi)較大的人力和物力。

網(wǎng)絡(luò)及通信技術(shù)的飛速發(fā)展，Internet越來(lái)越普及到人們的日常生活中，人們對(duì)Internet的需求也越來(lái)越大，Internet所帶來(lái)的好處也越來(lái)越得到體現(xiàn)，使許多的信息家電、智能儀表等非PC智能終端接入到互聯(lián)網(wǎng)成為可能，從而實(shí)現(xiàn)網(wǎng)絡(luò)化、智能化的集中管理。智能終端投入實(shí)際環(huán)境中運(yùn)行后，一部分在軟件開(kāi)發(fā)過(guò)程中無(wú)法充分測(cè)試的錯(cuò)誤便會(huì)暴露出來(lái);在智能終端的運(yùn)行期內(nèi)，用戶(hù)也往往會(huì)對(duì)智能終端軟件提出新的功能要求和性能要求。增量網(wǎng)絡(luò)編程可以通過(guò)遠(yuǎn)程通信的方式實(shí)現(xiàn)智能的自動(dòng)更新，有效降低了更新和維護(hù)成本。

1 增量網(wǎng)絡(luò)編程原理

增量網(wǎng)絡(luò)編程主要分為三個(gè)步驟:編碼、分發(fā)和解碼。在編碼階段，主控系統(tǒng)只讀入程序代碼并將每一行都保存在一個(gè)隊(duì)列中，并準(zhǔn)備分發(fā)的代碼包［1］。

在分發(fā)階段，主控系統(tǒng)將程序代碼以數(shù)據(jù)包的格式發(fā)送，智能終端將接收到的數(shù)據(jù)包存放在外部閃存中。由于網(wǎng)絡(luò)編程模塊以用戶(hù)級(jí)別運(yùn)行，無(wú)法直接將程序代碼寫(xiě)入程序存儲(chǔ)區(qū)，所以將其存放在外部閃存，同時(shí)智能終端請(qǐng)求主控系統(tǒng)重新傳送丟失的數(shù)據(jù)包。

寫(xiě)入到外部閃存的代碼包與初始的程序代碼具有相同的格式，在解碼階段，智能終端只要驗(yàn)證程序映像并調(diào)用BootLoader將程序代碼保存在程序存儲(chǔ)區(qū)。BootLoader是在系統(tǒng)內(nèi)核運(yùn)行之前運(yùn)行的一段小程序。通過(guò)這段小程序，可以初始化硬件設(shè)備、建立內(nèi)存空間的映射圖，從而將系統(tǒng)的軟硬件環(huán)境帶到一個(gè)合適的狀態(tài)，以便為最終調(diào)用系統(tǒng)內(nèi)核準(zhǔn)備好正確的環(huán)境。BootLoader具有向程序存儲(chǔ)區(qū)的用戶(hù)應(yīng)用程序部分寫(xiě)入數(shù)據(jù)的權(quán)限。然后重新啟動(dòng)系統(tǒng)，執(zhí)行最新建立的應(yīng)用程序。

圖1 增量網(wǎng)絡(luò)編程過(guò)程

為了設(shè)計(jì)一個(gè)增量網(wǎng)絡(luò)程序編程機(jī)制，需要考慮許多影響系統(tǒng)性能的因素。由于網(wǎng)絡(luò)編程時(shí)間與更新的數(shù)據(jù)量成正比，同時(shí)數(shù)據(jù)量也決定了傳輸數(shù)據(jù)的網(wǎng)絡(luò)成本，因此盡可能地降低更新的數(shù)據(jù)量可以縮短網(wǎng)絡(luò)編程的時(shí)間，降低使用成本。程序代碼存儲(chǔ)在外部閃存，而外部閃存的訪(fǎng)問(wèn)速度要遠(yuǎn)遠(yuǎn)低于片上存儲(chǔ)器，為了獲得更好的性能，應(yīng)該盡可能減少訪(fǎng)問(wèn)外部閃存。由于智能終端的處理能力有限，應(yīng)該將大部分處理放在主控系統(tǒng)執(zhí)行，而智能終端只處理最基本的操作［2］。

在外部閃存中，劃分兩塊存儲(chǔ)區(qū)域，一塊用于以前的程序映像，另一塊用于存儲(chǔ)將要建立的新映像(圖2)。其優(yōu)點(diǎn)在于可以提供相同的內(nèi)存映射并最小限度的影響B(tài)ootLoader代碼的重寫(xiě)。通過(guò)對(duì)BootLoader的修改，使其可以從由網(wǎng)絡(luò)編程模塊傳遞的基地址處讀取程序代碼。

圖2 存儲(chǔ)器組織結(jié)構(gòu)

2 基于Rsync算法的增量網(wǎng)絡(luò)編程

2.1 增量代碼的產(chǎn)生

對(duì)于增量網(wǎng)絡(luò)編程，通常使用的方法為:主控系統(tǒng)將程序映像文件分割為尺寸固定的塊，并比較以前版本和最新版本相應(yīng)的塊來(lái)獲得改變的程序塊(圖3)，將其稱(chēng)為固定塊比較。當(dāng)程序代碼映像移位時(shí)，固定塊比較無(wú)法找到相同的程序塊，因而該方法的效率不高。為此，采用Rsync算法［3］來(lái)產(chǎn)生增量并重建代碼映像。Rsync算法最初主要用于通過(guò)低帶寬網(wǎng)絡(luò)在兩個(gè)設(shè)備間進(jìn)行二進(jìn)制代碼的更新。

圖3 通過(guò)固定塊比較產(chǎn)生增量代碼

Rsync算法可以找出最新版本程序中哪些部分和原有程序中某個(gè)部分匹配，這部分的內(nèi)容就不需要通過(guò)網(wǎng)絡(luò)傳輸，需要的只是對(duì)原有程序相應(yīng)部分的引用，而新程序中無(wú)法匹配的部分就只能逐字傳輸。智能終端根據(jù)對(duì)原有程序的部分引用和逐字傳輸?shù)膬?nèi)容來(lái)構(gòu)造出新程序的一個(gè)副本。假設(shè)主控系統(tǒng)α的最新版本程序?yàn)镕new，智能終端β的原有程序?yàn)镕old，算法的步驟為:

(1)智能終端β將文件Fold分成互不重疊、尺寸固定的一系列數(shù)據(jù)塊，塊的尺寸為S字節(jié)，S∈［500，1000］，最后一個(gè)數(shù)據(jù)塊可能少于S字節(jié);

(2)智能終端β計(jì)算所有數(shù)據(jù)塊的校驗(yàn)和:32位的滾動(dòng)弱檢驗(yàn)和Ri以及128位的MD4強(qiáng)檢驗(yàn)和Mi，記為hi＜Ri，Mi＞。建立哈希表，對(duì)于每一對(duì)校驗(yàn)值，以滾動(dòng)校驗(yàn)和為關(guān)鍵值進(jìn)行哈希排序，并將哈希表傳送給主控系統(tǒng)α;

(3)主控系統(tǒng)α在文件Fnew中為所有長(zhǎng)度為S字節(jié)的數(shù)據(jù)塊(這些數(shù)據(jù)塊對(duì)于文件頭的位移量可以是任意的，不只是S的倍數(shù))計(jì)算滾動(dòng)校驗(yàn)和并與哈希表中的hi＜Ri，Mi＞中的Ri比較，發(fā)現(xiàn)與Ri相匹配的數(shù)據(jù)塊，再計(jì)算其強(qiáng)校驗(yàn)和與Mi比較，如果強(qiáng)校驗(yàn)和相等，說(shuō)明這兩個(gè)數(shù)據(jù)塊相同，記錄該數(shù)據(jù)塊的索引，即hash指示值，繼續(xù)比較下一個(gè)數(shù)據(jù)塊;如果不相等，說(shuō)明這兩個(gè)數(shù)據(jù)塊不同，則記錄該數(shù)據(jù)塊第一個(gè)字節(jié)，然后向后移動(dòng)一個(gè)偏移量，繼續(xù)比較，直到文件末尾;

(4)比較完成后，智能終端β收到主控系統(tǒng)α包含差異內(nèi)容和hash指示值的數(shù)據(jù)流，更新Fold，生成Fnew。

Rsync算法在新文件上進(jìn)行滑動(dòng)查找，移動(dòng)一個(gè)字節(jié)或一個(gè)塊長(zhǎng)。它能實(shí)現(xiàn)快速查找，很大部分要?dú)w功于采用了滾動(dòng)校驗(yàn)和。

圖4 差異增量的產(chǎn)生

2.2 智能終端程序的重構(gòu)

為了實(shí)現(xiàn)智能終端程序的更新，主控系統(tǒng)一般采用兩種操作來(lái)描述差異:Copy(CMD_COPY_BLOCK)和Download(CMD_DOWNLOAD_BLOCK)。在增量更新中，主控系統(tǒng)給每個(gè)匹配的模塊發(fā)送Copy報(bào)文，當(dāng)智能終端接收后，就將該數(shù)據(jù)塊從原有的映像中復(fù)制到當(dāng)前的映像［4］。對(duì)每個(gè)不匹配的模塊，主控系統(tǒng)發(fā)送一個(gè)或多個(gè)下載報(bào)文。

每個(gè)復(fù)制報(bào)文的數(shù)據(jù)尺寸為SREC行尺寸的倍數(shù)，而下載報(bào)文的數(shù)據(jù)尺寸為任意數(shù)值。當(dāng)下載報(bào)文的尺寸大于一個(gè)SREC行(16字節(jié))時(shí)，主控系統(tǒng)將其分為多個(gè)片段。

如果程序的結(jié)構(gòu)沒(méi)有改變時(shí)，程序映像的重構(gòu)比較簡(jiǎn)單。智能終端只需要寫(xiě)入下載模塊及執(zhí)行復(fù)制操作。當(dāng)程序映像發(fā)生偏移時(shí)，情況就會(huì)變得復(fù)雜。假設(shè)模塊從原有的映像中偏移了k位，并且k不是SREC行的整數(shù)倍［5］。這就導(dǎo)致數(shù)據(jù)塊橫跨兩個(gè)SREC行，需要兩次SREC行寫(xiě)入。為此可以采取下面的方法來(lái)解決:

當(dāng)下載的數(shù)據(jù)塊小于SREC行時(shí)，智能終端按照一行SREC寫(xiě)入，而不填充其他的數(shù)據(jù)。這時(shí)，將SREC行的尺寸設(shè)為實(shí)際的數(shù)據(jù)長(zhǎng)度(圖5)。復(fù)制數(shù)據(jù)塊時(shí)，從SREC行的起始位置進(jìn)行復(fù)制。這樣可以確保將每行數(shù)據(jù)塊復(fù)制到一個(gè)SREC行，同時(shí)將SREC行的SREC地址域改為在新映像中的偏移地址。

為能實(shí)現(xiàn)智能終端程序的自動(dòng)更新，我們對(duì)Rsync算法進(jìn)行了改進(jìn)，當(dāng)智能終端收到一個(gè)復(fù)制消息時(shí)，網(wǎng)絡(luò)編程模塊立即編譯執(zhí)行，無(wú)須將其放入隊(duì)列中。由于沒(méi)有保存腳本命令，所以當(dāng)有消息丟失時(shí)，網(wǎng)絡(luò)編程模塊必須檢查重構(gòu)的程序映像。因?yàn)椴恢纴G失的復(fù)制或下載消息是否導(dǎo)致丟失錯(cuò)誤，所以每次丟失記錄都要發(fā)送重傳請(qǐng)求，而這將額外花費(fèi)大量的時(shí)間。

為此，在智能終端中，將所有的腳本命令保存在隊(duì)列中，并檢查所有包含腳本命令的數(shù)據(jù)包是否丟失，當(dāng)智能終端接收到解碼消息后，就對(duì)腳本信息進(jìn)行解碼。

圖5 新程序映像重構(gòu)

2.3 改進(jìn)的Rsync算法

為了發(fā)送腳本命令，主控系統(tǒng)將每個(gè)腳本命令嵌入到CMD_DOWNLOADING消息中，而嵌入消息保存在外部閃存中，CID代表在腳本隊(duì)列中，SREC行的數(shù)量。為了使復(fù)制腳本與其他消息類(lèi)型區(qū)別，在 SREC類(lèi)型域使用了特殊數(shù)值。在SREC規(guī)定中，該域只允許使用幾個(gè)數(shù)值(0，1，2，3，5，7，8和9)，在這里使用10來(lái)代表一個(gè)嵌入的復(fù)制消息。這樣既可以使其具有與其他類(lèi)型的數(shù)據(jù)相同的存儲(chǔ)方式，又能夠確保正確的解釋復(fù)制命令。

圖6 CMD_DOWNLOADING格式

由于外部閃存有足夠的空間，使用外部閃存來(lái)存儲(chǔ)腳本命令，為此，將外部閃存分為三個(gè)部分:以前程序映像、新程序映像及腳本隊(duì)列。

主控系統(tǒng)以“下載”(CMD_DOWNLOADING)消息發(fā)送腳本，智能終端將這些腳本保存在腳本隊(duì)列中。當(dāng)主控系統(tǒng)查詢(xún)?nèi)魏蝸G失腳本命令時(shí)，智能終端掃描該腳本隊(duì)列。如果智能終端發(fā)現(xiàn)丟失記錄，則請(qǐng)求重新發(fā)送。主控系統(tǒng)響應(yīng)該請(qǐng)求，重新發(fā)送丟失的信息。智能終端接收到解碼命令后，開(kāi)始對(duì)腳本進(jìn)行解碼，分別將嵌入在腳本命令中的下載或復(fù)制命令提取出來(lái)，并對(duì)命令進(jìn)行相應(yīng)的解釋(圖7)。

3 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)環(huán)境下，綜合各方面的因素，按照前面設(shè)計(jì)的算法，實(shí)現(xiàn)了增量更新系統(tǒng)。實(shí)驗(yàn)時(shí)，一個(gè)主控端同時(shí)對(duì)三個(gè)智能終端進(jìn)行更新，結(jié)果表明改進(jìn)后的增量網(wǎng)絡(luò)編程，通過(guò)Rsync算法產(chǎn)生兩個(gè)程序的映像差異，再將差異部分傳輸給智能終端，達(dá)到快速地對(duì)智能終端編程的目的。以遠(yuǎn)程通信的方式實(shí)現(xiàn)智能的自動(dòng)更新。

圖7 解碼腳本命令

4 結(jié)束語(yǔ)

本文以智能終端的增量網(wǎng)絡(luò)編程為基礎(chǔ)，對(duì)Rsync算法進(jìn)行了改進(jìn)，實(shí)現(xiàn)智能終端的自動(dòng)更新，而且改進(jìn)后的算法沒(méi)有涉及任何具體的程序代碼，具有很好的移植性。

［1］Linda Wills.An open platform for recongurable control.IEEE Control Systems Magazine［J］.2001(6):34 －36.

［2］Rahul Kapur，Tom Yeh，Ujjwal Lahoti.Differential Wireless Reprogramming of Sensor Networks［J］.UCLA CS213 Project Report，2003(12):23 －25.

［3］Andrew Tridgell.Efficient Algorithms for Sorting and Synchronization［D］.Canberra:Australian National University，1999.

［4］Adam Chlipala，Jonathan Hui，Gilman Tolle.Deluge:Data Dissemination in Multi－ Hop Sensor Networks［J］.UC Berkeley CS294 －1 Project Report，2003(12):5 －9.

［5］SOURCE A.SANs sharing storage to infinity and beyond［J］.Electronic Design，2004，52(9):16 － 19.

［6］全勇，楊杰，鄧志鵬.基于增量余弦RBF網(wǎng)絡(luò)的慣性導(dǎo)航初始對(duì)準(zhǔn)［J］.上海交通大學(xué)學(xué)報(bào)，2002，36(12):35－38.