福建師范大學(xué) 林馨

隨著科技的發(fā)展和互聯(lián)網(wǎng)的普及，各種組織機構(gòu)的內(nèi)部人員常需要從互聯(lián)網(wǎng)獲得工作、學(xué)習(xí)等相關(guān)信息。通?？梢酝ㄟ^直接訪問外部網(wǎng)絡(luò)或?qū)⒊Ｓ脭?shù)據(jù)存儲到本地服務(wù)器以獲取信息，兩種方式都會產(chǎn)生一定的費用。本文將綜合兩種獲取信息的方式，從節(jié)約成本的角度，給出優(yōu)化策略。

1 問題

隨著現(xiàn)代科技的發(fā)展，網(wǎng)絡(luò)上的資訊也豐富多樣，互聯(lián)網(wǎng)成為我們學(xué)習(xí)工作生活中不可分割的部分。各種組織機構(gòu)，如學(xué)校、醫(yī)院、企業(yè)等日常都需要從網(wǎng)絡(luò)獲取各類信息，以提高工作效率，提升產(chǎn)品或服務(wù)的質(zhì)量等。

從網(wǎng)上獲取信息會產(chǎn)生網(wǎng)絡(luò)通信費。若機構(gòu)將一些經(jīng)常需要訪問的數(shù)據(jù)塊下載存儲到本地服務(wù)器，就可以節(jié)省部分由于訪問外網(wǎng)所產(chǎn)生的通信費用。同時我們注意到，購買以及維護本地服務(wù)器也需要一定的費用，因此我們要在二者之間找到平衡點，設(shè)計出既經(jīng)濟又合理的方案。

假設(shè)已知每個本地服務(wù)器的存儲容量、購買價格以及維護費用，機構(gòu)所要獲取的數(shù)據(jù)塊并以日常訪問頻次確定每個數(shù)據(jù)塊的重要性權(quán)重，以及從網(wǎng)絡(luò)獲取每個數(shù)據(jù)塊所需通信費用。如圖1 所示給出了內(nèi)網(wǎng)配置方案所需考慮的因素。

圖1 內(nèi)網(wǎng)配置方案需考慮的因素Fig.1 Factors for Intranet configuration scheme

引用[1]中已探討了當(dāng)數(shù)據(jù)塊不可分割且服務(wù)器中存儲單位數(shù)據(jù)量的成本相同時，購買服務(wù)器以及數(shù)據(jù)塊的存儲方案。本文將考查數(shù)據(jù)塊可分割存儲且服務(wù)器中存儲不同數(shù)據(jù)塊單位數(shù)據(jù)量的成本不同時，需要購買的服務(wù)器數(shù)量，選擇存儲哪些數(shù)據(jù)塊以及如何將數(shù)據(jù)塊存儲在服務(wù)器上，從而給出使機構(gòu)能獲取所需信息，同時又能節(jié)約成本的方案。

2 求解

設(shè)總共有m個數(shù)據(jù)塊，其中第i個數(shù)據(jù)塊的數(shù)據(jù)量為Qi,從外網(wǎng)獲得第i個數(shù)據(jù)塊時產(chǎn)生的通信費用為Bi,則第i個數(shù)據(jù)塊單位數(shù)據(jù)量的通信費是Fi=Bi/Qi.設(shè)每個服務(wù)器的存儲容量為W，價格是V，則服務(wù)器單位容量的價格為P=V/W。由于不同數(shù)據(jù)塊訪問頻次不同，服務(wù)器存儲第i個數(shù)據(jù)塊單位數(shù)據(jù)量的維護費為Si，因此服務(wù)器存儲第i個數(shù)據(jù)塊單位數(shù)據(jù)量的成本Ci=P+Si.

求解思路：對第i個數(shù)據(jù)塊的單位數(shù)據(jù)量而言，若訪問外網(wǎng)產(chǎn)生的通信費大于服務(wù)器存儲成本，即Fi>Ci時，則將第i個數(shù)據(jù)塊存儲到服務(wù)器；將滿足以上條件的所有數(shù)據(jù)塊歸為A 類并全部存儲在服務(wù)器中，從而確定需購買的服務(wù)器數(shù)量；若存儲了所有A 類數(shù)據(jù)塊后，服務(wù)器有剩余容量，則對剩余的滿足0.95Ci

我們先將數(shù)據(jù)塊歸為A 類以及B 類[1]。假設(shè)A 類共有t個數(shù)據(jù)塊，B 類共有k個數(shù)據(jù)塊。完成數(shù)據(jù)塊分類之后，我們利用貪心算法將數(shù)據(jù)塊存儲到服務(wù)器。

貪心算法[2]是通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇，并希望通過每次所作的貪心選擇導(dǎo)致最終結(jié)果是問題的一個最優(yōu)解。

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。貪心算法所作的貪心選擇可以依賴于以往所做過的選擇，但絕不依賴于將來所作的選擇，也不依賴于子問題的解。因此貪心算法是自頂向下，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。

一個典型的貪心算法如Kruskal 算法求簡單無向圖的最小生成樹：首先把所有頂點看作孤立點作為初始圖，將所有的邊權(quán)按從小到大排序，每次選出權(quán)值最小的邊，若加入該邊不產(chǎn)生回路，就將其加到圖中，直到得到最小生成樹，如圖2 所示。

圖2 Kruskal 算法求圖(a)的最小生成樹(f)Fig.2 Kruskal algorithm for MST (f) of graph (a)

將數(shù)據(jù)塊存入服務(wù)器的基本步驟：（1）將A 類數(shù)據(jù)塊存到服務(wù)器。首先，將A 類數(shù)據(jù)塊按Fi-Ci的值降序排列；之后，按順序?qū)?shù)據(jù)塊存入服務(wù)器：若當(dāng)前數(shù)據(jù)塊數(shù)據(jù)量不超過當(dāng)前服務(wù)器剩余容量，則直接存儲；若當(dāng)前數(shù)據(jù)塊數(shù)據(jù)量超過當(dāng)前服務(wù)器剩余容量，則將此數(shù)據(jù)塊分割，一部分填滿當(dāng)前服務(wù)器，另一部分存入下一個服務(wù)器；重復(fù)這個過程，直到將A 類數(shù)據(jù)塊全部存儲直服務(wù)器，這時統(tǒng)計所需服務(wù)器數(shù)量以及服務(wù)器剩余容量。（2）將部分B 類數(shù)據(jù)塊存儲到服務(wù)器。首先，將B 類數(shù)據(jù)塊按Ci-Fi升序排列；之后按順序?qū)?shù)據(jù)塊存入服務(wù)器：若當(dāng)前數(shù)據(jù)塊數(shù)據(jù)量不超過當(dāng)前服務(wù)器剩余容量，則直接存儲；若當(dāng)前數(shù)據(jù)塊數(shù)據(jù)量超過當(dāng)前服務(wù)器剩余容量，則將此數(shù)據(jù)塊分割，一部分填滿當(dāng)前服務(wù)器。至此，所有A 類數(shù)據(jù)塊和部分B 類數(shù)據(jù)塊已存入服務(wù)器。

算法1：將A 類數(shù)據(jù)塊存儲到服務(wù)器。

Step1. 將A 類數(shù)據(jù)塊按Fi-Ci的值降序排序[3]，得D1,D2,...Dt，i=j=1，Wj=W；

step2. 若i>t，則轉(zhuǎn)step4；否則，轉(zhuǎn)step3；

step3. 若Di

step4.n=j，停止。

我們由算法1 知，共需要n個服務(wù)器，在存儲了A類數(shù)據(jù)塊中總共t個數(shù)據(jù)塊之后,服務(wù)器Ln的剩余容量為Wn，如圖3 所示。

圖3 A 類數(shù)據(jù)塊存入服務(wù)器的三種情形Fig.3 Threeways type A data stores at servers

雖然B 類數(shù)據(jù)塊的單位數(shù)據(jù)量所產(chǎn)生的通信費小于服務(wù)器單位容量的存儲成本，但若是存儲完A 類數(shù)據(jù)塊，服務(wù)器仍有剩余空間，我們將部分B 類數(shù)據(jù)塊存入可充分利用服務(wù)器的存儲空間。

算法2：將B 類數(shù)據(jù)塊存儲到服務(wù)器的剩余空間。

Step1. 將B 類數(shù)據(jù)塊按Ci-Fi的值升序排序[3]，得D1,D2,...Dk，i=1；

step2. 若Wn=0，則停止；否則，轉(zhuǎn)step3；

step3. 若Di

Step4. 若i>k,s=i-1,停止；否則，轉(zhuǎn)step3。

由算法1、算法2 知，服務(wù)器總共存儲了A 類共t個數(shù)據(jù)塊，以及B 類共s個數(shù)據(jù)塊，且服務(wù)器無法再存儲B 類中剩余數(shù)據(jù)塊,如圖4 所示。至此，服務(wù)器存儲了A 類中所有數(shù)據(jù)塊以及B 類中部分?jǐn)?shù)據(jù)塊，其余需要數(shù)據(jù)都通過訪問外網(wǎng)獲得，產(chǎn)生通信費用。

圖4 數(shù)據(jù)塊存入服務(wù)器的總體方案Fig.4 Overall scheme for data storage at servers

3 結(jié)語

本文通過優(yōu)化算法給出了將哪些數(shù)據(jù)塊存儲到本地服務(wù)器以及存儲的方案，從而使得組織機構(gòu)能在較低的成本下，為其內(nèi)部成員提供所需的數(shù)據(jù)信息。由于從網(wǎng)絡(luò)上獲取信息存在風(fēng)險，而計算機系統(tǒng)是通過多個防御層來防止遭受惡意活動的攻擊，包括政策(安全審核、個人使用限制、培訓(xùn)等)和技術(shù)(防火墻、反病毒、入侵檢測系統(tǒng)、漏洞掃描、數(shù)據(jù)冗余等)在內(nèi)的防御措施，將會對機構(gòu)的風(fēng)險類型產(chǎn)生各種影響。因此，在本文的基礎(chǔ)上，還可進一步探討機構(gòu)網(wǎng)絡(luò)安全策略，即在盡量減少成本的前提下選擇適當(dāng)?shù)姆烙胧?/p>