降低inrane網(wǎng)訪問費(fèi)用的策略

降低inrane網(wǎng)訪問費(fèi)用的策略

1直接的訪問頻率另一個(gè)商業(yè)網(wǎng)絡(luò)，即intranet網(wǎng)絡(luò)，具有兩個(gè)功能。在互聯(lián)網(wǎng)上，我們必須積極發(fā)布信息，介紹最新產(chǎn)品和技術(shù)，向公眾披露公司，并采取預(yù)防措施來賺取巨額利潤(rùn)。內(nèi)部，它是一個(gè)互聯(lián)網(wǎng)用戶。為了充分了解市場(chǎng)，有必要訪問內(nèi)部網(wǎng)絡(luò)之外的信息。為在商業(yè)競(jìng)爭(zhēng)中保持有利地位,面對(duì)如此浩翰無垠的Internet信息和來自企業(yè)內(nèi)外眾多的訪問請(qǐng)求,必須設(shè)法有效地組織和規(guī)劃內(nèi)部網(wǎng)的信息資源,以達(dá)到減輕服務(wù)器負(fù)擔(dān)、降低訪問費(fèi)用、提高Intranet網(wǎng)使用效率等目的。為了便于理解,可歸納成如下兩個(gè)問題加以論述。(1)一般情況下,在企業(yè)內(nèi)部分布信息時(shí),總是在邏輯上將相應(yīng)的信息主題分成塊結(jié)構(gòu),使內(nèi)容彼此獨(dú)立的信息組成不同的信息塊。這些信息塊分布在企業(yè)內(nèi)部不同的Web服務(wù)器上。由于各信息塊內(nèi)容不同,其重要性及被感興趣的程度不同,因此它們被訪問的頻率也必然不同。如果這些信息塊毫無規(guī)律地安置在各Web服務(wù)器上,必將使各個(gè)服務(wù)器被訪問的頻率有顯著差別。最極端的情況則是其中的一兩臺(tái)服務(wù)器被頻繁訪問,甚至有可能因負(fù)擔(dān)過重而擁塞,而其它服務(wù)器則顯得“門前冷落”。一旦出現(xiàn)這種情況,最直接的后果是資源浪費(fèi),此外,因?yàn)轭l繁地告訴用戶“因訪問者太多,請(qǐng)您稍后再試”等信息,會(huì)使網(wǎng)上用戶對(duì)此節(jié)點(diǎn)失去耐心,從而失去某些無形資產(chǎn),所以有必要對(duì)各信息塊被訪問的頻率進(jìn)行統(tǒng)計(jì),在此基礎(chǔ)上建立數(shù)學(xué)模型,確定解決方案,使各服務(wù)器所承受的負(fù)擔(dān)盡可能均衡,防止造成訪問瓶頸。(2)Intranet用戶必然同時(shí)也是Internet的用戶,面對(duì)豐富多彩的Internet信息資源,他們會(huì)頻繁地訪問Internet網(wǎng)絡(luò)。由于企業(yè)對(duì)Internet信息訪問是有針對(duì)性的,有其明顯的目的,所以必然只對(duì)其中的一些信息資源感興趣,訪問也比較頻繁,從而使通信費(fèi)用增長(zhǎng)。另一方面,有不同的用戶會(huì)對(duì)相同的信息主題產(chǎn)生興趣,以至于屢屢擊入相同的網(wǎng)址調(diào)用這些信息,同樣也會(huì)使通信費(fèi)用增長(zhǎng)。為了有效地降低通信費(fèi)用,可以將那些被頻繁訪問的Internet信息下載至Intranet內(nèi)部的Web服務(wù)器上,使之成為內(nèi)部信息,Intranet用戶可在內(nèi)部對(duì)其進(jìn)行訪問。一旦成為內(nèi)部信息,其通信費(fèi)用和訪問速度就不可同日而語了。所以也必須在統(tǒng)計(jì)的基礎(chǔ)上,建立數(shù)學(xué)模型,確定解決方案,切實(shí)有效地降低通信費(fèi)用,提高訪問速度。顯然,上述兩個(gè)問題是基于Intranet的分布式信息系統(tǒng)信息組織和規(guī)劃的關(guān)鍵問題。前者是針對(duì)內(nèi)部信息的組織安放的,可概括為訪問瓶頸問題;后者則是針對(duì)外部通信的,稱為通信費(fèi)用問題。本文將就這兩個(gè)問題分別提出其數(shù)學(xué)模型和求解方法。2可用模型和解決方案2.1waaa首先對(duì)訪問瓶頸問題作如下描述:將一定數(shù)量的信息塊存放到規(guī)定數(shù)目的服務(wù)器上,由于各信息塊被訪問的次數(shù)不同,存放的原則是使各服務(wù)器被訪問的次數(shù)盡可能相等。在數(shù)學(xué)上,這是一個(gè)集合劃分問題(setpartitioningproblem,SPP)。所謂集合劃分問題,是指將一給定集合劃分為指定個(gè)數(shù)互不相交的子集,并使每個(gè)子集含有的元素大小之和盡可能一致。它的判定問題嚴(yán)格敘述為:(SPP)實(shí)例:有窮集合A={a1,a2,…,an},以及每一個(gè)a∈A的“大小”w(a)∈R+;正整數(shù)m∈Z+,問:是否存在一個(gè)關(guān)于A的劃分σ={A1,A2,…,Am}使得?j=1,2,…,m,有∑a∈AjW(a)=1m∑a∈AW(a)∑a∈AjW(a)=1m∑a∈AW(a)由此,訪問瓶頸問題可以形式化地描述為:將一給定的信息主題集合A={a1,a2,…,an}(n個(gè)信息主題)劃分為m個(gè)互不相交的子集(即分配至m臺(tái)服務(wù)器),并使每個(gè)子集(服務(wù)器)含有的元素大小(受訪問頻率)之和盡可能一致。在實(shí)際應(yīng)用中,訪問頻率w(a)可由統(tǒng)計(jì)軟件來測(cè)量。它具有一定的穩(wěn)定性,同時(shí)也因?yàn)楦鞣N因素影響(如信息的老化、經(jīng)濟(jì)因素、政策政治因素等)而呈現(xiàn)動(dòng)態(tài)變化,因此w(a)是一個(gè)與時(shí)間等參數(shù)有關(guān)的函數(shù),但w(a)有一定的統(tǒng)計(jì)規(guī)律可循,在一定的時(shí)間段內(nèi)是穩(wěn)定的。當(dāng)采集到的w(a)發(fā)生變化時(shí),后面提及的算法可動(dòng)態(tài)地調(diào)整對(duì)文件的分配。在數(shù)學(xué)上,稱使各子集中元素大小之和盡可能一致的SPP為SPP優(yōu)化問題。對(duì)于它,人們通常從兩個(gè)方面來考慮。其一是使最大的子集最小化(記為minimax-SPP),另一是使最小的子集最大化(記為maximin-SPP)。下面給出其數(shù)學(xué)描述。以正數(shù)集P={p1,p2,…,pn}代替A,其中p代表pi的大小;P劃分成σ={M1,M2,…,Mm}個(gè)子集,同時(shí)Ci代表Mi中元素之和。那么,minimax-SPP定義為:minimize(maxCi);maximin-SPP定義為maximize(minCi)其中σ為P的任一劃分。2.2lpt算法自本世紀(jì)以來,人們一直致力于構(gòu)造一些好的性能保證多項(xiàng)式時(shí)間近似算法。本文采用其中最自然也是最有名的LPT(longestprocessingtime)算法。LPT算法的思想敘述如下.(1)把元素按單調(diào)遞減順序排列,不妨設(shè)P1≥P2≥P3…≥Pn,構(gòu)成序列L;(2)將L中的當(dāng)前元素放入當(dāng)前和最小的子集中,然后從L中去掉它。2.3創(chuàng)建應(yīng)問題的最優(yōu)劃分記σ={M1,M2,…,Mm}為由LPT得到的劃分,s+={M+1,M+2,…,M+m}為相應(yīng)問題的最優(yōu)劃分,并且分別記Mj和M+j的元素和為Cj和C+j,令M=maxCj,W=minCj;M+=maxC+j,W+=minC+j;則有對(duì)于minimax-SPPMM+≤43?13mΜΜ+≤43-13m對(duì)于maximin-SPPWW+≥3m?14m?2WW+≥3m-14m-22.4關(guān)于spp-lpbpb的算法描述在企業(yè)專用網(wǎng)內(nèi),因?yàn)槊總€(gè)部門均有自己的Web服務(wù)器。在一般情況下,與本部門有關(guān)的信息塊將存放在該部門的Web服務(wù)器上,以便于使用和管理。也就是說,有可能會(huì)指定某些信息塊必須存放在確定的服務(wù)器上。針對(duì)這種情況,相應(yīng)地,可將SPP進(jìn)一步推廣,這便是帶核集劃分問題,簡(jiǎn)稱為NSPP。在數(shù)學(xué)上,可將它描述如下。有限集A={p1,p2,…,pn}∪{g1,g2,…,gm},其中P={p1,p2,…,pn}是非核元集,稱對(duì)應(yīng)的信息主題為非核信息主題集。G={g1,g2,…,gm}為核元集,稱對(duì)應(yīng)信息主題為核信息主題集。它與SPP的區(qū)別在于在A的劃分σ={M1,M2,…,Mm}中,必須有g(shù)j∈Mj+?j對(duì)核元gj,要求gj非負(fù)。于是類似地得到兩個(gè)問題:maximin-NSPP和minimax-NSPP。當(dāng)LPT應(yīng)用它們時(shí),首先放置gj于Mj,然后再按LPT放置非核元。這樣的經(jīng)過修正的稱LPT為MLPT。同樣,maximin-NSPP和minimax-NSPP也有一個(gè)性能問題。再次引用上一節(jié)中的標(biāo)記M,M+,W,W+,則有對(duì)于minimax-NSPPmm+≤32?12mmm+≤32-12m對(duì)于maximin-NSPPww+≥2m?13m?2ww+≥2m-13m-2在數(shù)學(xué)上,算法的分析必須考慮到最壞情況。但是,在工程上這種極端的情況是很少出現(xiàn)的。所以,引入LPT和MLPT算法就能有效地解決訪問瓶頸問題?？梢岳霉ぞ哕浖?首先對(duì)各帶核和不帶核的信息主題進(jìn)行統(tǒng)計(jì)和分析,在此基礎(chǔ)上對(duì)各信息主題進(jìn)行優(yōu)化組合,使得各Web服務(wù)器信息量分布合理,負(fù)擔(dān)均衡,并使資源合理配置,達(dá)到Intranet穩(wěn)定有效運(yùn)行之目的。3通信成本問題的數(shù)學(xué)模型和解決方案3.1通信費(fèi)用ss首先將通信費(fèi)用問題作如下描述:現(xiàn)企業(yè)內(nèi)部網(wǎng)中有一節(jié)點(diǎn)專門用來存放從外部調(diào)入的信息。因該節(jié)點(diǎn)容量有限,問怎樣有目的地選擇信息放入節(jié)點(diǎn),在不超過最大容量的情況下,使節(jié)點(diǎn)的使用效率最高。在數(shù)學(xué)上,這是一個(gè)背包問題(KNAPSACK),背包問題的數(shù)學(xué)描述如下。設(shè)有一位旅行家,在出發(fā)前準(zhǔn)備一只背包,限制背包內(nèi)物體的總重量不超過b?，F(xiàn)有n類物體p1,p2,…,pn,pi類中每個(gè)物體的重量為wi價(jià)值為vi,1≤i≤n,物體不能拆開。問怎樣把物體放入背包內(nèi),在不超重的條件下使背包內(nèi)物體的總價(jià)值最大?設(shè):xi={01?0xi={01?0表示不裝入背包,1表示裝入背包,則背包問題可歸納為下列數(shù)學(xué)問題:目標(biāo)函數(shù):maxz=∑i=1nviximaxz=∑i=1nvixi;約束條件:∑i=1nwixi≤b∑i=1nwixi≤b,求滿足約束條件并使目標(biāo)函數(shù)值最大的解(x1,x2,…,xn)。由此,通信費(fèi)用問題可以形式化地描述為:設(shè)在內(nèi)部網(wǎng)Intranet之外有n個(gè)信息塊,其信息量大小為S,對(duì)某個(gè)信息塊每調(diào)用一次的費(fèi)用為F,這里考慮到信息的有償服務(wù)附加因素,假定對(duì)不同站點(diǎn)、不同信息調(diào)用的費(fèi)用也不相同。本文提出的通信費(fèi)用實(shí)際上是單純的通信費(fèi)用和信息服務(wù)費(fèi)等附加費(fèi)用的總和,從而調(diào)用信息的通信費(fèi)用與信息容量的大小不一定成正比。費(fèi)率因子R=Fi/Si不為常數(shù);還可以用統(tǒng)計(jì)軟件獲得每個(gè)信息量為Si的信息塊在一定時(shí)間內(nèi)的訪問次數(shù)Ti,現(xiàn)在要選擇部分信息單元調(diào)入內(nèi)部網(wǎng)某一站點(diǎn)a,a所允許的最大容量為M。則在信息內(nèi)容不能全部調(diào)入的情況下,問怎樣把一些信息單元調(diào)入a,在不超過最大容量的情況下,a內(nèi)信息的實(shí)用價(jià)值最大?設(shè)xi={01,0xi={01,0表示不調(diào)入內(nèi)部網(wǎng),1表示調(diào)入內(nèi)部網(wǎng)。則通信費(fèi)用問題可歸納為下列數(shù)學(xué)問題:目標(biāo)函數(shù):maxz=∑i=1nviximaxz=∑i=1nvixi;約束條件:∑i=1nSixi≤M∑i=1nSixi≤Μ,求滿足約束條件并使目標(biāo)函數(shù)值最大的解(x1,x2,…,xn)。這里,vi=Fi*Ti表示所調(diào)入a的信息,若費(fèi)用越高訪問次數(shù)越多,則實(shí)用價(jià)值越大。3.2信息塊的剩余容量在數(shù)學(xué)上,背包問題可以用很多算法求解,其中最直觀的算法是“貪婪算法”。它是依照一種最優(yōu)度量法即每步都取局部最優(yōu)值最后求得解的過程。對(duì)應(yīng)通信費(fèi)用問題,其算法思想可以簡(jiǎn)單描述如下:先把要調(diào)入內(nèi)部網(wǎng)的各信息塊按visivisi的比值排序,比值高的信息塊排在前面,比值較低的排在后面,呈遞減序列。然后盡量挑選比值大的信息塊先調(diào)入a,即按遞減序列將各信息塊依次調(diào)入a,到最后可能還剩余部分容量小于按順序該調(diào)入a的信息塊的容量。此時(shí),依次比較其后的每一個(gè)信息塊,直到找到一個(gè)可放入的為止。若所有的信息塊容量均大于剩余容量,則前面調(diào)入a的信息塊即為解。“貪婪算法”雖然很直觀,但是它的解并不一定是最優(yōu)解,有時(shí)甚至與最優(yōu)解相距甚遠(yuǎn),誤差超過可以忍受的范圍。所以,在精度較高的場(chǎng)合下一般使用分枝定界算法。該算法對(duì)一切可能的狀態(tài)逐個(gè)搜索比較將出現(xiàn)指數(shù)型的復(fù)雜性。因?yàn)楸疚闹饕抢眠@種算法解決工程問題,所以必須綜合考慮精度和復(fù)雜性,在兼顧兩方面因素的前提下,采用一種近似算法,其算法主要的思想如下。(1)問題的解由向量(x1,x2,…,xn)表示,取部分向量(x1,x2,…,xk)表示部分解,k<n,此時(shí)a內(nèi)信息總量為∑i=1kSixi∑i=1kSixi,存在以下兩種情況。①存在某個(gè)j>k,使得M?∑i=1kSixi≥SiΜ-∑i=1kSixi≥Si,這表示在a內(nèi)還可以放入某個(gè)信息塊而容量不至于超過M,則依次比較最后—個(gè)下載信息塊之后的量,直到找到一個(gè)放得下的信息塊為止。若還有剩余容量,則作循環(huán),直到所有的任何信息塊均比較完;②對(duì)于所有j>k?M?∑i=1kSixi≤Sij>k?Μ-∑i=1kSixi≤Si,這說明在a內(nèi)已不能放入任何一個(gè)信息塊,否則會(huì)超過M,則j>k時(shí),xi=0。(2)取部分向量(x1,x2,…,xk,xk+1)表示部分解,轉(zhuǎn)以上步驟,其中h為小于n的整數(shù),IM存放最佳結(jié)果的I,當(dāng)k≠0時(shí),k個(gè)元素的子集數(shù)目為(nk)<nk,(n0)=1,∑k=0k(nk)≤∑k=0knk=nk+1?1n?1=0(nk)(nk)<nk,(n0)=1,∑k=0k(nk)≤∑k=0knk=nk+1-1n-1=0(nk),故近似算法的復(fù)雜性為O(nk+1)。3.3通信費(fèi)用問題的近似算法設(shè)通信費(fèi)用算法的最優(yōu)解為Z+,上述算法的解為Z?？梢宰C明:Z+?ZZ<1n+1Ζ+-ΖΖ<1n+1。該算法的性能與h的取值有關(guān)。當(dāng)h≥h+時(shí),Z=Z+,即近似算法得出的解是最優(yōu)解;當(dāng)h<h+時(shí),此時(shí)近似算法不能保證一定獲得最優(yōu)解。通過引入背包問題及其解法,成功地解決了通信費(fèi)用問題。它具有精度高,容易用程序?qū)崿F(xiàn)等優(yōu)點(diǎn),對(duì)于企業(yè)內(nèi)部網(wǎng)具有重要的實(shí)際意義。4中小企業(yè)內(nèi)部網(wǎng)容量不能匹