【正文】 標(biāo)準(zhǔn)進(jìn)行打包，經(jīng)過 IP 網(wǎng)絡(luò)把數(shù) 據(jù)包送至接受地，再把這些語音數(shù)據(jù)包串起來，經(jīng)過解碼解壓處理后，恢復(fù)成原來的語音信號(hào)，從而達(dá)到由互聯(lián)網(wǎng)傳送語音的目的。 1 圖的矩陣表示方法 ： 圖的幾何表示具有直觀性。圖的矩陣表示則適于數(shù)值計(jì)算和分析，可存入計(jì)算機(jī)。圖的矩陣表示與幾何表示一一對(duì)應(yīng)。 關(guān)聯(lián)矩陣：是表達(dá)端與邊的關(guān)聯(lián)性的矩陣。 鄰接陣 :它是表達(dá)端與端之間的關(guān)系矩陣。 數(shù)據(jù)結(jié)構(gòu)中算法的時(shí)間復(fù)雜度的計(jì)算方法 ： 對(duì)算法的評(píng)價(jià)主要關(guān)心計(jì)算復(fù)雜度，也就是花時(shí)間的長短。計(jì)算復(fù)雜度與循環(huán)的次數(shù)有關(guān)，循環(huán)次數(shù)通常跟邊 的數(shù)目和點(diǎn)的數(shù)目有關(guān)。所以一般情況下用邊的數(shù)目和點(diǎn)的數(shù)目的數(shù)學(xué)復(fù)雜度來表示計(jì)算復(fù)雜度。 一個(gè)算法的時(shí)間復(fù)雜度 (Time Complexity)是指該算法的運(yùn)行時(shí)間與問題規(guī)模的對(duì)應(yīng)關(guān)系。一個(gè)算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行的時(shí)間取決于二者的綜合效果。為了便于比較同一問題的不同算法，通常把算法中基本操作重復(fù)執(zhí)行的次數(shù)（頻度）作為算法的時(shí)間復(fù)雜度。算法中的基本操作一般是指算法中最深層循環(huán)內(nèi)的語句，因此，算法中基本操作語句的頻度是問題規(guī)模 n 的某個(gè)函數(shù) f(n)，記作：T(n)=O(f(n))。其中“ O”表示隨問題 規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長率和 f(n)的增長率相同，或者說，用“ O”符號(hào)表示數(shù)量級(jí)的概念。例如，如 )1n(n21)n(T?=，則 )1n(n21?的數(shù)量級(jí)與 n2 相同，所以 T(n)=O（ n2）。 如果一個(gè)算法沒有循環(huán)語句，則算法中基本操作的執(zhí)行頻度與問題規(guī)模 n 無關(guān)，記作 O(1)，也稱為常數(shù)階。如果算法只有一個(gè)一重循環(huán)，則算法的基本操作的執(zhí)行頻度與問題規(guī)模 n 呈線性增大關(guān)系，記作 O（ n），也叫線性階。常用的還有平方階 O（ n2）、立方階 O（ n3）、對(duì)數(shù)階 O(log2n)等。 設(shè)無向圖 G 有 n 個(gè)頂點(diǎn)和 m 條邊， 因?yàn)?DFS 對(duì)鄰接表中的每個(gè)節(jié)點(diǎn)最多檢查一次，共有 2m個(gè)節(jié)點(diǎn)，所以執(zhí)行時(shí)間為 O（ m） ,若是用鄰接矩陣表示則為 O(n^2)。 圖算法： warshall 算法：用于求可達(dá)性矩陣，時(shí)間復(fù)雜度為 O（ n^3/2）；深度優(yōu)先算法：查找某個(gè)特定的點(diǎn)或者邊，時(shí)間復(fù)雜度為 O（ b^m）？ (b 為分支系統(tǒng)， m 為圖的最大深度 )； Dijkstra 算法：初始圖為有向圖，解決有向圖中最短最輕路徑問題，以點(diǎn)為依據(jù)，有根節(jié)點(diǎn)選擇，時(shí)間復(fù)雜度為 O（ n^2）， n 為點(diǎn)的個(gè)數(shù)。（因?yàn)檎麠l路為最輕路，故顯然存在累加計(jì)算） 遍歷圖 的時(shí)間復(fù)雜度和深度優(yōu)先相同，用鄰接矩陣表示則為 O(n^2)。 BFS(寬度 /廣度優(yōu)先 ) 1 function Dijkstra(G, w, s) 2 for each vertex v in V[G] 3 d[v] := infinity 4 previous[v] := undefined 5 d[s] := 0 6 S := empty set 7 Q := set of all vertices 8 while Q is not an empty set 9 u := Extract_Min(Q) 10 S := S union {u} 11 for each edge (u,v) outgoing from u 12 if d[v] d[u] + w(u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u 行 24 的初始化對(duì) n 個(gè)頂點(diǎn)進(jìn)行，顯然是 O（ n） ； 56行 O（ 1） ； 7 行 n 個(gè)頂點(diǎn)入隊(duì)列 O（ n） ； 8 行 14 行，從 8 行可以看出進(jìn)行了 n 遍循環(huán)，每遍在第九行調(diào)用一次 ExtractMin 過程， ExtractMin 過程需要搜尋鄰接表，每一次需要搜尋整個(gè)數(shù)組，所以一次操作時(shí)間是 O(n)。11 行到 14 行對(duì)節(jié)點(diǎn) u 的鄰接表中的邊進(jìn)行檢查，總共有 |E|次（總共 .每條邊最多檢查一次 )，因此是 O(E)；合起來就是O（ E+n*n） = O（ n^2)； 以 上合起來就是 O（ n） +O（ 1） +O（ n） +O（ n^2） == O（ n^2)。 1 約束路由計(jì)算 方法 約束路由 是一種命令驅(qū)動(dòng)并具有資源預(yù)留能力的 路由算法 ，能夠和現(xiàn)有的 Inter 中的拓?fù)潋?qū)動(dòng)的、逐跳的 內(nèi)部網(wǎng)關(guān)協(xié)議 共存。它可以根據(jù)多個(gè)約束條件（可以是 QOS 約束條件也可以是其他策略性的約束條件）計(jì)算出所有的可能路徑并根據(jù)一定的優(yōu)選策略選出一條最優(yōu)的路徑，實(shí)現(xiàn)網(wǎng)絡(luò)性能的優(yōu)化。 1 MST（最小生成樹）求解初始樹的增廣圖 ?如果存在一節(jié)點(diǎn) w：（ 1）所有源都有邊連接到 w；（ 2） w 有邊連接到所有的宿和中間節(jié)點(diǎn)。則初試樹以 w 為中心 。 ?如果不存在這類節(jié)點(diǎn) w，人為增加邊或節(jié)點(diǎn)。 ?并為邊（ ij）關(guān)聯(lián)懲罰函數(shù) ijp ： 0?ijp 原有邊； 1?ijp 人為增加邊。初始樹求解，變換為附加問題： ? ijijxpMin 。 相關(guān)符號(hào)： y：累計(jì)成本（行）； A：關(guān)聯(lián)矩陣； x：分配流大小可行解（列）； b：需求向量（ 列）； c：成本向量（行）。 代數(shù)符號(hào)說明 ： (1)從樹 T 開始，求可行解 x。向量 x，包括每條邊上分配流的大小；（ 2） step1 中，對(duì)每個(gè)節(jié)點(diǎn)計(jì)算累計(jì)成本值。（ a）jiji ycy ?? Tij?? ；（ b）向量 y，記錄節(jié)點(diǎn)分配流的大小。（ 3） C 為成本向量； b 為需求向量； A 為關(guān)聯(lián)矩陣； Ax=b。 Step1(添加邊的選擇 )：（ 1）定義： yAcc ??39。 （ 39。c 為邊成本與所分配流的差）；（ 2） if Tij? then 039。 ???? jiijij yycc 。if 039。 ?? ijcTij 且 then ij 為候選邊； Also if Tij? then 0?ijx 。綜合以上關(guān)系，有： )00,(0 39。39。 ???? ijij o rxe ith e rcijxc .(3)對(duì)于可行解 )0,( 39。39。39。 ?? xbAxx ，其成本為： ybxcy A xxcxyAccx ?????? 39。39。39。39。39。39。39。39。 )( ；（ 4）對(duì)于 x，其成本為：)0( 39。39。 ???? xcybybxccx 。（ 5）將 yb 用 cx 替代，有 （舊樹成本）新樹成本 cxxccx ?? 39。39。39。 )( （ 1）。（ 6）所以， if 39。39。39。 ,0 xxc ? 是比 x 更好的解。 Step2（代數(shù)表示） ：（ 1）找到 邊 e=uv， 滿足： )0..( 39。 ??? uvvuvu ceiycy 。（ 2）如果無此邊， then 039。?c and so 039。39。 ?xc ，則 equation(1)喻示對(duì)于 所有可行解 39。x ，都有 cxcx?39。 ，即 x 為最優(yōu)。（ 3）如果有此邊 e，將其加入到樹 T。Step3( 代數(shù)表示 ) ：（ 1 ） T+e 存 在 一 個(gè) 圈 。 依 照 e 的 方 向 ， 將 圈 中 的 邊 分 為 前 向 和 反 向 邊 設(shè) 置（不在圈中）；反向邊；前向邊 ij)()( xtxtxx ijijij ??? 。（ 2）因 t? 相互抵消， bAxAx ??39。 。所以，選擇合適的 t，滿足 ,039。?x 則 39。x 是可行解。（ 3）因只有 e 滿足 0?ijc 且 0?ijx ，所以： tccxxc e39。39。39。 ?? 。問 題變換為選擇 t，使用 39。x 為可行解，并減少 39。cx 。由于 ,039。 ?cc 減少 39。cx 就是增長 t。（ 4）為保證 39。x 為可行解（ . 039。?x ），需要找到反向邊 f，該邊具有最小值 fx ,得到 fxt? 。（ 5）可行解 39。x ，有 039。 ?fx ，因此 f 為移除邊。移除邊 f，正好解除了 T+e 中的圈，因此 T+ef 對(duì)應(yīng)于新可行解 39。x 。 1 業(yè)務(wù)流量增長預(yù)測方法 ： ① logistic 分布函數(shù)： 用戶數(shù) p(t), 隨 時(shí) 間 的 變 化 ， 正 比 于 已 有 用 戶 數(shù) ， 與 待 發(fā) 展 用 戶 數(shù) 之 積 ， 即 ：))(1)(()()( tptprdtpdtp ??????? ,或 )1(/ pprdtdp ??? （（ 1p） 待發(fā)展用戶數(shù)即潛在用戶）， pz /1? 代入上式，則有)1()1)/1(()/1)(1(/)/1(/ 22 ?????????????? zrprppprdtdppdtdz 所以， ))exp(1/(1 rtp ??? (r 反應(yīng)斜率，增長速度 )。（ 2/1,0。0,。1, ?????????? ptptpt ） ② Gompertz 模型： 死亡率是兩項(xiàng)之和，一項(xiàng)與人的年齡無關(guān)，一項(xiàng)與年齡有關(guān)。（ 1 ）不考慮與 年齡無關(guān)項(xiàng)：)/1ln ()(/ ppbdxdp ??? 存活時(shí)間 ；（ 2）概率密度函數(shù)： )exp( bxbx eeeb ?? ? ? ；（ 3）累計(jì)概率函數(shù)： ))1(exp(1 ??? bxe? ；（ 4）等價(jià)表示： ?? ? ?? xexh )( )]e x p ()/e x p [ ln ()( 0 tKpKtp ??? 。 下面說明： SNtw網(wǎng)絡(luò)用戶總數(shù)， GLTE和 GLTE為單用戶流量增長 無線寬帶流量預(yù)測：總增長率來自 HSPA 滲透率和 LTE 新用戶滲透率： )()()( ttt PDPLTEHS PATotal ??； 總業(yè)務(wù)流量： )()()( ttt TTTLTEHS PATotal ??；其中， LTE 部分： )()()( ttt GPSTLTELTENtwLTE ?； HSPA 部分： )()]()([)()()( tttttt GPPSGDSTHSP ALTET o ta lN twHSP AHSP AN twHSP A ??? 1 固定容量設(shè)備選址問題： ?接入帶寬需求及定義： J：匯聚節(jié)點(diǎn)集； ih ：節(jié)點(diǎn) i 的帶寬需求； ijc ：節(jié)點(diǎn) i 匯聚到節(jié)點(diǎn) j 成本； jp ：匯聚節(jié)點(diǎn)計(jì)算成本； jF ：匯聚節(jié)點(diǎn)建造成本； jb ：匯聚節(jié)點(diǎn)寬帶。 ?目標(biāo)函數(shù)最?。?? ??? ?? ??Ni Jj ijjijiJj jj xpchyFMi ni m ize 1 )( 1/0?jy ：節(jié)點(diǎn) j 安裝匯聚設(shè)備 so that:（ 1）jNi iji bxh ???1 for Jj? (容量約束：每個(gè)接入節(jié)點(diǎn)容量之和 匯聚節(jié)點(diǎn)容量 )；（ 2） 0???Jj ijx for i=1,2,...,N.(接入約束：只能連到一個(gè)匯聚節(jié)點(diǎn) )；（ 3） jij yx? for Jj? and i=1,2,...,N Jforjy j ?? },1,0{ Jforjxij ?? },1,0{ and i=1,2,...,N(不可接入約束 )。 1 無線信號(hào)覆蓋的最優(yōu)化建模：（室內(nèi)微小區(qū)覆蓋問題） 最小化： _ _ _ _ _ _11( , ) [ [ ( , ) m ax { 0 , ( , ) } ] ]m i i iif x y p x y p x y sm? ?? ? ?? 平均損耗最小 + _ _ _ _1( 1 )[ [ m ax [ ( , ) m ax { 0 , ( , ) } ]]]jni i iiSj p x y p x y s? ??? ? ?? 最大損耗最小 用戶站點(diǎn) i，總數(shù) m， 基站 j，位置 ( , )jjxy ，總數(shù) n， 路徑損耗 : ( , ) m in { ( , ) }i j i j jp x y g x y? , ( , ) ( , )arg m i n ( ( , )){ | } l o g ( ( , ))1 . . . . . . , 1 . . . . . . i j j a i j ji j i j jje i j jg x y f N x yi g x ysi n d x yi m j n ??? ??? 穿墻；自由空間 1 M/M/1 系統(tǒng) N= [(T1+T2)/2] [2/L2] =T ? =N 平均逗留延時(shí) :???? 1T 平均逗留用戶數(shù)： N=???? 平均服務(wù)時(shí)間?1 平均等待延時(shí) :W=?1?T 平均等待用戶數(shù)：?????? 12WNQ 利用率因子???? 24 臺(tái)計(jì)算機(jī)，各自平均每秒發(fā)出 48 個(gè)分組 ,分組長度符合負(fù)指分布，平均為 125Bytes； 共享占用 T1()線路； 方案一： 24 臺(tái)計(jì)算機(jī)，按 TDM，各占 1 個(gè)時(shí)隙 (8bit)； 方案二： 24 臺(tái)計(jì)算機(jī)，按 STDM，占 24 個(gè)時(shí)隙 (192bit) 方案 一：看做 24 個(gè) M/M/1 : (15448)/24=64 Kbits 平均分組長度： L=125*8=1Kbit（ 1Byte=8Bit） 平均分組發(fā)送速率： mu=64Kbps/L= 64 packets/s 。