【正文】 標準進行打包，經(jīng)過 IP 網(wǎng)絡把數(shù) 據(jù)包送至接受地，再把這些語音數(shù)據(jù)包串起來，經(jīng)過解碼解壓處理后，恢復成原來的語音信號，從而達到由互聯(lián)網(wǎng)傳送語音的目的。 1 圖的矩陣表示方法 ： 圖的幾何表示具有直觀性。圖的矩陣表示則適于數(shù)值計算和分析，可存入計算機。圖的矩陣表示與幾何表示一一對應。 關聯(lián)矩陣：是表達端與邊的關聯(lián)性的矩陣。 鄰接陣 :它是表達端與端之間的關系矩陣。 數(shù)據(jù)結構中算法的時間復雜度的計算方法 ： 對算法的評價主要關心計算復雜度，也就是花時間的長短。計算復雜度與循環(huán)的次數(shù)有關，循環(huán)次數(shù)通常跟邊 的數(shù)目和點的數(shù)目有關。所以一般情況下用邊的數(shù)目和點的數(shù)目的數(shù)學復雜度來表示計算復雜度。 一個算法的時間復雜度 (Time Complexity)是指該算法的運行時間與問題規(guī)模的對應關系。一個算法是由控制結構和原操作構成的，其執(zhí)行的時間取決于二者的綜合效果。為了便于比較同一問題的不同算法，通常把算法中基本操作重復執(zhí)行的次數(shù)（頻度）作為算法的時間復雜度。算法中的基本操作一般是指算法中最深層循環(huán)內(nèi)的語句，因此，算法中基本操作語句的頻度是問題規(guī)模 n 的某個函數(shù) f(n)，記作：T(n)=O(f(n))。其中“ O”表示隨問題 規(guī)模 n 的增大，算法執(zhí)行時間的增長率和 f(n)的增長率相同，或者說，用“ O”符號表示數(shù)量級的概念。例如，如 )1n(n21)n(T?=，則 )1n(n21?的數(shù)量級與 n2 相同，所以 T(n)=O（ n2）。 如果一個算法沒有循環(huán)語句，則算法中基本操作的執(zhí)行頻度與問題規(guī)模 n 無關，記作 O(1)，也稱為常數(shù)階。如果算法只有一個一重循環(huán)，則算法的基本操作的執(zhí)行頻度與問題規(guī)模 n 呈線性增大關系，記作 O（ n），也叫線性階。常用的還有平方階 O（ n2）、立方階 O（ n3）、對數(shù)階 O(log2n)等。 設無向圖 G 有 n 個頂點和 m 條邊， 因為 DFS 對鄰接表中的每個節(jié)點最多檢查一次，共有 2m個節(jié)點，所以執(zhí)行時間為 O（ m） ,若是用鄰接矩陣表示則為 O(n^2)。 圖算法： warshall 算法：用于求可達性矩陣，時間復雜度為 O（ n^3/2）；深度優(yōu)先算法：查找某個特定的點或者邊，時間復雜度為 O（ b^m）？ (b 為分支系統(tǒng)， m 為圖的最大深度 )； Dijkstra 算法：初始圖為有向圖，解決有向圖中最短最輕路徑問題，以點為依據(jù)，有根節(jié)點選擇，時間復雜度為 O（ n^2）， n 為點的個數(shù)。（因為整條路為最輕路，故顯然存在累加計算） 遍歷圖 的時間復雜度和深度優(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 的初始化對 n 個頂點進行，顯然是 O（ n） ； 56行 O（ 1） ； 7 行 n 個頂點入隊列 O（ n） ； 8 行 14 行，從 8 行可以看出進行了 n 遍循環(huán)，每遍在第九行調用一次 ExtractMin 過程， ExtractMin 過程需要搜尋鄰接表，每一次需要搜尋整個數(shù)組，所以一次操作時間是 O(n)。11 行到 14 行對節(jié)點 u 的鄰接表中的邊進行檢查，總共有 |E|次（總共 .每條邊最多檢查一次 )，因此是 O(E)；合起來就是O（ E+n*n） = O（ n^2)； 以 上合起來就是 O（ n） +O（ 1） +O（ n） +O（ n^2） == O（ n^2)。 1 約束路由計算 方法 約束路由 是一種命令驅動并具有資源預留能力的 路由算法 ，能夠和現(xiàn)有的 Inter 中的拓撲驅動的、逐跳的 內(nèi)部網(wǎng)關協(xié)議 共存。它可以根據(jù)多個約束條件（可以是 QOS 約束條件也可以是其他策略性的約束條件）計算出所有的可能路徑并根據(jù)一定的優(yōu)選策略選出一條最優(yōu)的路徑，實現(xiàn)網(wǎng)絡性能的優(yōu)化。 1 MST（最小生成樹）求解初始樹的增廣圖 ?如果存在一節(jié)點 w：（ 1）所有源都有邊連接到 w；（ 2） w 有邊連接到所有的宿和中間節(jié)點。則初試樹以 w 為中心 。 ?如果不存在這類節(jié)點 w，人為增加邊或節(jié)點。 ?并為邊（ ij）關聯(lián)懲罰函數(shù) ijp ： 0?ijp 原有邊； 1?ijp 人為增加邊。初始樹求解，變換為附加問題： ? ijijxpMin 。 相關符號： y：累計成本（行）； A：關聯(lián)矩陣； x：分配流大小可行解（列）； b：需求向量（ 列）； c：成本向量（行）。 代數(shù)符號說明 ： (1)從樹 T 開始，求可行解 x。向量 x，包括每條邊上分配流的大?。唬?2） step1 中，對每個節(jié)點計算累計成本值。（ a）jiji ycy ?? Tij?? ；（ b）向量 y，記錄節(jié)點分配流的大小。（ 3） C 為成本向量； b 為需求向量； A 為關聯(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 。綜合以上關系，有： )00,(0 39。39。 ???? ijij o rxe ith e rcijxc .(3)對于可行解 )0,( 39。39。39。 ?? xbAxx ，其成本為： ybxcy A xxcxyAccx ?????? 39。39。39。39。39。39。39。39。 )( ；（ 4）對于 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)喻示對于 所有可行解 39。x ，都有 cxcx?39。 ，即 x 為最優(yōu)。（ 3）如果有此邊 e，將其加入到樹 T。Step3( 代數(shù)表示 ) ：（ 1 ） T+e 存 在 一 個 圈 。 依 照 e 的 方 向 ， 將 圈 中 的 邊 分 為 前 向 和 反 向 邊 設 置（不在圈中）；反向邊；前向邊 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 對應于新可行解 39。x 。 1 業(yè)務流量增長預測方法 ： ① logistic 分布函數(shù)： 用戶數(shù) p(t), 隨 時 間 的 變 化 ， 正 比 于 已 有 用 戶 數(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 反應斜率，增長速度 )。（ 2/1,0。0,。1, ?????????? ptptpt ） ② Gompertz 模型： 死亡率是兩項之和，一項與人的年齡無關，一項與年齡有關。（ 1 ）不考慮與 年齡無關項：)/1ln ()(/ ppbdxdp ??? 存活時間 ；（ 2）概率密度函數(shù)： )exp( bxbx eeeb ?? ? ? ；（ 3）累計概率函數(shù)： ))1(exp(1 ??? bxe? ；（ 4）等價表示： ?? ? ?? xexh )( )]e x p ()/e x p [ ln ()( 0 tKpKtp ??? 。 下面說明： SNtw網(wǎng)絡用戶總數(shù)， GLTE和 GLTE為單用戶流量增長 無線寬帶流量預測：總增長率來自 HSPA 滲透率和 LTE 新用戶滲透率： )()()( ttt PDPLTEHS PATotal ??； 總業(yè)務流量： )()()( ttt TTTLTEHS PATotal ??；其中， LTE 部分： )()()( ttt GPSTLTELTENtwLTE ?； HSPA 部分： )()]()([)()()( tttttt GPPSGDSTHSP ALTET o ta lN twHSP AHSP AN twHSP A ??? 1 固定容量設備選址問題： ?接入帶寬需求及定義： J：匯聚節(jié)點集； ih ：節(jié)點 i 的帶寬需求； ijc ：節(jié)點 i 匯聚到節(jié)點 j 成本； jp ：匯聚節(jié)點計算成本； jF ：匯聚節(jié)點建造成本； jb ：匯聚節(jié)點寬帶。 ?目標函數(shù)最小： ? ??? ?? ??Ni Jj ijjijiJj jj xpchyFMi ni m ize 1 )( 1/0?jy ：節(jié)點 j 安裝匯聚設備 so that:（ 1）jNi iji bxh ???1 for Jj? (容量約束：每個接入節(jié)點容量之和 匯聚節(jié)點容量 )；（ 2） 0???Jj ijx for i=1,2,...,N.(接入約束：只能連到一個匯聚節(jié)點 )；（ 3） jij yx? for Jj? and i=1,2,...,N Jforjy j ?? },1,0{ Jforjxij ?? },1,0{ and i=1,2,...,N(不可接入約束 )。 1 無線信號覆蓋的最優(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? ??? ? ?? 最大損耗最小 用戶站點 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 平均逗留延時 :???? 1T 平均逗留用戶數(shù)： N=???? 平均服務時間?1 平均等待延時 :W=?1?T 平均等待用戶數(shù)：?????? 12WNQ 利用率因子???? 24 臺計算機，各自平均每秒發(fā)出 48 個分組 ,分組長度符合負指分布，平均為 125Bytes； 共享占用 T1()線路； 方案一： 24 臺計算機，按 TDM，各占 1 個時隙 (8bit)； 方案二： 24 臺計算機，按 STDM，占 24 個時隙 (192bit) 方案 一：看做 24 個 M/M/1 : (15448)/24=64 Kbits 平均分組長度： L=125*8=1Kbit（ 1Byte=8Bit） 平均分組發(fā)送速率： mu=64Kbps/L= 64 packets/s 。