董燦 吳峻峰

摘 要 對于員工經(jīng)常到外面執(zhí)行任務(wù)的大公司或大機構(gòu)來說，員工通過移動設(shè)備來同步任務(wù)數(shù)據(jù)要消耗很多數(shù)據(jù)流量和造成服務(wù)器很大的負載開銷。通過利用P2P技術(shù)，本文的分布式數(shù)據(jù)同步協(xié)議可以讓組隊外出的員工減少數(shù)據(jù)流量的消耗和服務(wù)器負載開銷，主要原理包括兩層：一層是相同部分的數(shù)據(jù)不需要所有員工的移動設(shè)備都和服務(wù)器同步，只要部分員工有同步，其他人就可以用P2P技術(shù)在便攜式熱點建立的局域網(wǎng)內(nèi)同步；第二層是通過積分獎勵來鼓勵員工避開服務(wù)器負載高峰期進行提前的數(shù)據(jù)同步，讓服務(wù)器在負載高峰期可以減少負擔。本文還對提出的協(xié)議給出了數(shù)學算法，并分析了其算法復雜度。

【關(guān)鍵詞】移動數(shù)據(jù)同步 優(yōu)化 分布式 協(xié)議

1 導言

考慮下述應用場景：假設(shè)某公司或機構(gòu)經(jīng)常派員工到城郊各地去執(zhí)行工作任務(wù)，并且外部的工作環(huán)境無法提供無線網(wǎng)絡(luò)，使得外出的員工只能通過移動網(wǎng)絡(luò)來同步工作表單數(shù)據(jù)和任務(wù)資料。在這種應用場景中，如果這些員工是組隊外出的，那么他們就可以用根據(jù)本文的數(shù)據(jù)同步優(yōu)化協(xié)議實現(xiàn)的APP來減少在移動網(wǎng)絡(luò)中耗費的數(shù)據(jù)流量。這對公司或機構(gòu)的數(shù)據(jù)服務(wù)器端也是好事，原因是前述員工們在移動網(wǎng)絡(luò)中耗費的數(shù)據(jù)流量都對應著服務(wù)器要承擔的數(shù)據(jù)同步任務(wù)，而流量的減少意味著服務(wù)器負載的下降。這使得服務(wù)器因為負載過高而產(chǎn)生卡頓甚至宕機的機率大為減少。

為了解決該場景中的移動端數(shù)據(jù)流量和服務(wù)器負載優(yōu)化問題，我們可以使用P2P技術(shù)。P2P是peer-to-peer的縮寫，又稱對等網(wǎng)絡(luò)，可以簡單的定義成通過直接交換來共享計算機資源和服務(wù)，而對等計算模型應用層形成的網(wǎng)絡(luò)通常稱為對等網(wǎng)絡(luò)。在P2P網(wǎng)絡(luò)環(huán)境中，彼此連接的計算機處于對等的地位。網(wǎng)絡(luò)中的每一臺計算機既能充當網(wǎng)絡(luò)服務(wù)的請求者，又對其它計算機的請求作出響應，提供資源和服務(wù)。對等網(wǎng)絡(luò)又稱工作組，網(wǎng)上各臺計算機有相同的功能，無主從之分，一臺計算機都是既可作為服務(wù)器，設(shè)定共享資源供網(wǎng)絡(luò)中其他計算機所使用，又可以作為工作站，沒有專用的服務(wù)器，也沒有專用的工作站。

近年來，移動對等網(wǎng)絡(luò)的關(guān)鍵技術(shù)成為研究的熱點。其中，由于移動網(wǎng)絡(luò)的流量限制，對等網(wǎng)絡(luò)中的自私節(jié)點的檢測和激勵機制成為一個重要問題。在本文所提到的問題的求解中，我們通過一些任務(wù)分配和激勵機制來防止自私節(jié)點的出現(xiàn)，從而保證減少移動端數(shù)據(jù)流量和服務(wù)器負載的目標能夠合理地實現(xiàn)。

利用P2P技術(shù)，本文提出數(shù)據(jù)同步優(yōu)化協(xié)議稱為移動網(wǎng)絡(luò)局部協(xié)同數(shù)據(jù)同步優(yōu)化協(xié)議，其原理基于下述基本思想：

（1）移動設(shè)備，包括手機和支持SIM卡的平板，可以通過建立便攜式網(wǎng)絡(luò)熱點來組建臨時的局域網(wǎng)；

（2）數(shù)據(jù)同步時，去同一個地方的員工很可能需要同步若干相同的數(shù)據(jù)，而一份相同的數(shù)據(jù)沒必要每臺移動設(shè)備都和服務(wù)器同步一遍，完全可以一臺移動設(shè)備同步之后，其它移動設(shè)備通過臨時的局域網(wǎng)來局部同步，從而減少移動網(wǎng)絡(luò)數(shù)據(jù)流量；

（3）去同一地點執(zhí)行任務(wù)的某些員工可能已經(jīng)在其移動設(shè)備上有部分的最新數(shù)據(jù)，這些最新數(shù)據(jù)有可能是員工在外出前就利用無線網(wǎng)或數(shù)據(jù)線同步到移動設(shè)備上的，而其他員工如果也需要這些數(shù)據(jù)但沒有提前同步的話，可以利用臨時的局域網(wǎng)內(nèi)的數(shù)據(jù)分享來免流量同步；

（4）為了合理地分配遠程數(shù)據(jù)同步的任務(wù)，這些移動設(shè)備可以在臨時的局域網(wǎng)內(nèi)交換數(shù)據(jù)供求信息，然后按照需求協(xié)商分配消費移動數(shù)據(jù)流量的遠程數(shù)據(jù)同步任務(wù)，原則包括：

1.對于每一份不同的數(shù)據(jù)，只有對這份數(shù)據(jù)有需求的移動設(shè)備才需要承擔相應的遠程數(shù)據(jù)同步任務(wù)；

2.在前一條原則的基礎(chǔ)上，遠程數(shù)據(jù)同步任務(wù)盡可能均勻，使流量的消費盡可能平均的平攤到不同的移動設(shè)備上；

3.對于當次無法完全平攤的流量消費，可以做歷史記錄，在以后的局部協(xié)同數(shù)據(jù)優(yōu)化中，可根據(jù)歷史記錄來為前面承擔較多遠程數(shù)據(jù)同步任務(wù)的移動設(shè)備適當減少任務(wù)；

（5）對于外出前提前進行部分數(shù)據(jù)同步的員工，應根據(jù)以下原則給予數(shù)據(jù)同步上的獎勵：

1.提前數(shù)據(jù)同步時越是避開服務(wù)器的負載高峰期，得到的獎勵就越多；

2.在用便攜式熱點組建臨時局域網(wǎng)時，為其他人提供的有效數(shù)據(jù)共享越多，得到的獎勵就越多；

3.上述兩種獎勵都是積分制的，提前同步過程加分，獎勵兌換過程減分，其中獎勵的兌換是讓相應的移動設(shè)備在平攤遠程同步任務(wù)時可以用分數(shù)來兌換承擔量。

根據(jù)上述基本思想，本文剩余部分將按如下結(jié)構(gòu)來細述協(xié)議的規(guī)則和數(shù)學模型：第二節(jié)解釋提前進行同步的積分加分規(guī)則，并且給出分析規(guī)則加分量的數(shù)學模型；第三節(jié)描述在平攤遠程同步任務(wù)時的積分兌換規(guī)則；第四節(jié)闡述遠程同步任務(wù)的分攤過程數(shù)學模型，并且為該數(shù)學模型設(shè)計一套計算機算法；第五節(jié)分析前面三節(jié)中的算法的計算復雜度；最后一節(jié)是本文的總結(jié)，給出本文的結(jié)論。

2 提前同步加分規(guī)則

如果一位員工在執(zhí)行外出任務(wù)前提前同步部分相關(guān)的數(shù)據(jù)，那么在執(zhí)行任務(wù)時通過移動網(wǎng)絡(luò)局部協(xié)同數(shù)據(jù)同步優(yōu)化協(xié)議來和其他員工一起同步數(shù)據(jù)時，就可以得到減少平攤遠程同步任務(wù)的獎勵。該獎勵有以下規(guī)則：

（1）只有在進行協(xié)同數(shù)據(jù)同步時其他員工有需求的那些提前同步數(shù)據(jù)，其提前同步者才能獲得加分。如果其他員工沒有對某份數(shù)據(jù)的需求，那么即使該員工提前同步了該數(shù)據(jù)，他也不能從這份數(shù)據(jù)的提前同步中獲得加分。

（2）在進行協(xié)同數(shù)據(jù)同步時，如果有很多參與在其中的員工對某份數(shù)據(jù)都有需求，那么對該份數(shù)據(jù)的提前同步就可以獲得較高的分數(shù)；反之，如果只有少數(shù)參與者對該份數(shù)據(jù)有需求，那么對該份數(shù)據(jù)的提前同步就只能獲得較低的分數(shù)。

（3）在進行協(xié)同數(shù)據(jù)同步時，如果有多名參與者都提前同步了某份數(shù)據(jù)，那么他們共享這份數(shù)據(jù)時的加分倍數(shù)變小。一份數(shù)據(jù)提前同步的參與者越多，意味著這份數(shù)據(jù)的需求越易預測，因此分攤到單名提前同步該數(shù)據(jù)的參與者上時，加的分數(shù)會變少。

（4）提前同步的時機會影響加分的分數(shù)。如果提前同步的時間處于公司或機構(gòu)的服務(wù)器的低負載時段，那么提前同步加分的倍數(shù)就可以得到較大的獎勵加成；反之如果提前同步的時間處于服務(wù)器的高負載時段，那么提前同步的加分倍數(shù)就會較少。

（5）協(xié)同數(shù)據(jù)同步時服務(wù)器的當前負載率也會影響加分的分數(shù)。當前負載率高則表示要同步數(shù)據(jù)很困難，因此提前同步加分的倍數(shù)就應該大；反之當前負載率低則提前同步加分的倍數(shù)應該小。

（6）一份數(shù)據(jù)的提前同步加分，還和這份數(shù)據(jù)的大小有關(guān)。數(shù)據(jù)量大，表明為協(xié)同數(shù)據(jù)同步參與者節(jié)省的流量多，同時也為公司或機構(gòu)的服務(wù)器節(jié)省了較多的占用帶寬。因此，數(shù)據(jù)量較大的數(shù)據(jù)提前同步，可以得到的加分的倍數(shù)就會較大；反之數(shù)據(jù)量小的加分倍數(shù)也小。

（7）盡管不同數(shù)據(jù)的提前同步所得的加分是分開計算的，這些加分最終會按照員工與員工之間的互助關(guān)系合并在一起來兌換平攤遠程同步任務(wù)時的獎勵。換句話說，這些分數(shù)會按員工a為員工b提供了多少提前同步的幫助的分數(shù)形式來兌換，而兌換方法是員工b要通過遠程同步任務(wù)來反過來幫助員工a。

根據(jù)上述規(guī)則，我們可以知道為了用一個數(shù)學函數(shù)來描述一次協(xié)同數(shù)據(jù)同步過程中的加分，我們需要與這次協(xié)同數(shù)據(jù)同步相關(guān)的以下輸入數(shù)據(jù)：

1.這次協(xié)同數(shù)據(jù)同步中被至少一位參與者需求的數(shù)據(jù)的集合D1，D2，…，Dn；

2.參與這次協(xié)同數(shù)據(jù)同步的員工u1，u2，…， uk；

3.每份數(shù)據(jù)Di的需求者人數(shù)mi，以及每位員工uj需要的數(shù)據(jù)的編號集合Qj={ij1，ij2，…， }；

4.每份數(shù)據(jù)Di的提前同步供應者人數(shù)ki；

5.對于每份數(shù)據(jù)Di，上述每位員工uj在同步該數(shù)據(jù)過程的服務(wù)器平均負載率rij；如果uj沒有提前同步Di，則rij=+∞；

6.協(xié)同數(shù)據(jù)同步過程中當前的服務(wù)器負載率r；

7.每份數(shù)據(jù)Di的大小si。

假設(shè)用xij來表示數(shù)據(jù)供應者uj從提前同步數(shù)據(jù)Di中獲得的分數(shù)，用yjt來表示員工uj通過提前同步數(shù)據(jù)幫助員工ut所得的加分（稱為uj對ut的幫助分），那么規(guī)則1表示xij>0僅當mi>0且rij<+∞；規(guī)則2表示xij關(guān)于mi單調(diào)遞增；規(guī)則3表示xij關(guān)于ki單調(diào)遞減；規(guī)則4表示rij越大會使xij越小，并且rij=+∞時xij=0；規(guī)則5表示r越大會使xij越大；規(guī)則6表示xij關(guān)于si單調(diào)遞增；規(guī)則7表示

顯然xij的具體表達式可以有很多不同的方案?？紤]到移動設(shè)備主要不是用來計算的，我們盡可能地讓xij的表達式容易計算。我們采用如下的式子：

其中數(shù)據(jù)編號i=1，…，n，員工編號j=1，…，k.容易驗證這條式子滿足前述加分規(guī)則的要求。另外，由幫助分yjt的表達式可以知道yjt=-ytj。

3 積分兌換規(guī)則

如前所述，對于外出執(zhí)行任務(wù)前提前同步數(shù)據(jù)的員工，在協(xié)同數(shù)據(jù)同步過程中可以獲得積分的獎勵。這些獎勵按照如下的規(guī)則進行：

（1）如果前述的員工uj對員工ut的幫助分為負分，則員工uj可以通過承擔遠程數(shù)據(jù)同步任務(wù)來填補這個負分，而員工ut則可以獲得部分減免遠程數(shù)據(jù)同步任務(wù)的獎勵。

（2）并不是所有遠程數(shù)據(jù)同步任務(wù)都可以填補負幫助分。對于數(shù)據(jù)Di，只有當它同時是員工uj和ut需要的數(shù)據(jù)（亦即i同時在集合Qj和Qt內(nèi)）時，員工uj才可以通過承擔數(shù)據(jù)Di的遠程同步任務(wù)來填補他對員工ut的負幫助分。

（3）員工uj通過承擔數(shù)據(jù)Di的遠程同步任務(wù)，可以獲得用來填補負幫助分的兌換分=mi si. 該況換分將在Di的需求者之間平均分攤來兌換幫助分，因此這mi個需求者中的每一個都得到該數(shù)據(jù)si的兌換分。

（4）兌換分和幫助分的地位是平等的。這些分數(shù)在執(zhí)行這次協(xié)同數(shù)據(jù)同步后可能還有剩余，剩余部分將記入歷史記錄。這些記錄都是按員工與員工之間的互助關(guān)系來記錄的。

4 遠程同步任務(wù)分攤規(guī)則

遠程任務(wù)的分攤，有兩大規(guī)則：

（1）剩余的自由兌換分盡可能少，從而提前同步數(shù)據(jù)所得的幫助分可以得到最大程度的兌換；

（2）自由兌換分要盡可能地均勻分布到參與協(xié)同數(shù)據(jù)同步的員工上。

這兩條規(guī)則可能會沖突。在發(fā)生沖突時，優(yōu)先按第一條規(guī)則來實施。

為了建立這些任務(wù)分攤規(guī)則的數(shù)學模型，我們使用以下的符號：

1.協(xié)同數(shù)據(jù)同步中相關(guān)的數(shù)據(jù)集合D1，D2，…，Dn；

2.每份數(shù)據(jù)Di的大小si；

3.參與這次協(xié)同數(shù)據(jù)同步的員工u1，u2，…， uk；

4.每份數(shù)據(jù)Di的需求者人數(shù)mi，以及每位員工uj需要的數(shù)據(jù)的編號集合Qj={ij1，ij2，…， }；

5.由第二節(jié)的規(guī)則計算，根據(jù)公式（1）所得的uj對ut的當次幫助分yjt；

6.第三節(jié)的規(guī)則5和規(guī)則6所提到的uj對ut的歷史數(shù)據(jù)記錄的過往累積分數(shù)hjt（hjt=-htj）；

7.沒有人提前同步的數(shù)據(jù)Di的序號i的集合Q0；

8.在員工u1，u2，…，uk之間對集合Q0的分劃，其中對每個j=1，…，k，都要求， 并且當j≠t時，有.

利用以上的符號，可以把任務(wù)分攤規(guī)則的目標定義為幫助分得到盡可能多的兌換，其需要最小化的目標函數(shù)的數(shù)學表示為

由此可知該任務(wù)分攤的最優(yōu)化是一個組合優(yōu)化問題。這種問題求最優(yōu)解的計算復雜度太高，不太適合在不是以計算為主要目的的移動設(shè)備上計算。因此，我們退而求其次地設(shè)計一種貪心算法，用較少的計算量來取得一個比較好的結(jié)果就可以了。

我們設(shè)計的貪心算法有三層循環(huán)：外層循環(huán)如圖1中的流程圖所示，每循環(huán)一次從Q0中選出一個i，加入到已分配的數(shù)據(jù)編號集合中；中層循環(huán)負責為當次的外層循環(huán)從Q0選擇新的i，因此中層循環(huán)遍歷的Q0中還未被分配的i；內(nèi)層循環(huán)則負責為中層循環(huán)當前的i遍歷所有分配的可能，計算出該i對目標函數(shù)的貢獻。具體來說，如果外層循環(huán)先后選擇了Q0中的數(shù)據(jù)編號

內(nèi)層循環(huán)通過比較，為這i0個編號分別分配了編號為

的用戶來負責該數(shù)據(jù)的遠程同步任務(wù)，則如果記

argmin部分是中層循環(huán)，min部分是內(nèi)層循環(huán)。

5 算法的計算復雜度

第二節(jié)中的算法要對每一對j和t來計算xjt，而j和t的取值范圍為1到k，因此第二節(jié)的算法的復雜度為O（k2）。

第四節(jié)的算法有三層循環(huán)：外層循環(huán)總共n0次；在第t次外層循環(huán)中，中層循環(huán)共有n0-t+1次；在每次中層循環(huán)中，內(nèi)層循環(huán)的次數(shù)都是O（k），但每次內(nèi)層循環(huán)都要對每一對j和t來計算近似目標函數(shù)，而j和t的取值范圍為1到k，因此每次中層循環(huán)的復雜度為O（k3）。 綜上可知，第四節(jié)的算法的復雜度為O（n02k3）。

6 結(jié)論

本文給出了一種基于便攜式熱點的移動通信協(xié)同數(shù)據(jù)同步協(xié)議。該協(xié)議通過兩種方法來為用戶減少移動網(wǎng)絡(luò)的數(shù)據(jù)流量，為服務(wù)器端減少負載壓力：

（1）利用熱點局域網(wǎng)絡(luò)進行數(shù)據(jù)共享，盡可能地避免多位用戶重復下載他們共同需要的數(shù)據(jù)；

（2）利用積分制來鼓勵避開服務(wù)器負載高峰期提前同步數(shù)據(jù)，避免用戶的數(shù)據(jù)同步集中在一起，造成服務(wù)器的負載過高。

同時，本文還根據(jù)給出的協(xié)議建立了數(shù)學模型和計算機算法，使該協(xié)議能夠在實際應用中使用。

參考文獻

[1]黃桂敏，周婭，武小年.對等網(wǎng)絡(luò)[M].北京：科學出版社，2011.

[2]歐中洪，宋美娜，戰(zhàn)曉蘇等.移動對等網(wǎng)絡(luò)關(guān)鍵技術(shù)[J].軟件學報，2008，19（02）：404-418.

[3]牛新征.移動對等網(wǎng)絡(luò)若干關(guān)鍵技術(shù)的研究[D].電子科技大學，2008.

[4]秦娣.移動對等網(wǎng)絡(luò)關(guān)鍵技術(shù)分析[J]. 技術(shù)與市場，2015，22（12）：207-207.

[5]曲大鵬，王興偉，黃敏.移動對等網(wǎng)絡(luò)中自私節(jié)點的檢測和激勵機制[J].軟件學報，2013，24（04）：887-899.

作者簡介

董燦（1981-），男，云南省楚雄市人。畢業(yè)于南開大學，現(xiàn)任中國南方電網(wǎng)有限責任公司信息部規(guī)劃建設(shè)處主管，工程師。研究方向為企業(yè)信息系統(tǒng)建設(shè)及技術(shù)管控，數(shù)據(jù)質(zhì)量治理及信息系統(tǒng)實用化研究。

吳峻峰（1980-），男，廣東省廣州市人。中山大學博士，中山大學講師。研究方向為高性能計算、大數(shù)據(jù)、分布式計算。

作者單位

1.中國南方電網(wǎng)有限責任公司 廣東省廣州市 510530

2.中山大學 廣東省廣州市 510275