光纖網(wǎng)絡的弧負載指標及波長分配問題.pdf

1、光纖網(wǎng)絡是當今及未來信息網(wǎng)絡的核心技術之一，主要適用于可視電話、遠程教育、遠程醫(yī)療、家庭辦公等新型業(yè)務。光纖網(wǎng)絡可用一個弧對稱(即圖中有一條從u到v的弧當且僅當存在一條從v到u的弧)的有向連通圖表示，其路由集是滿足所有業(yè)務需求集的有向傳輸路徑的集合。給定一個路由集R，其點(或弧)負載指標(ForwardingIndex)定義為R中通過每個頂點(或弧)的路徑數(shù)目的最大值。進一步地，圖G的點(或弧)負載指標為滿足業(yè)務需求集的所有可能路由集的

2、點(或弧)負載指標的最小值，記為ξ(G)(或(π)(G))。光網(wǎng)絡中的路由問題(TheRoutingProblem)是指構造一個路由集，使得此路由集的弧負載指標達到最少。給定網(wǎng)絡的一個業(yè)務需求集，我們需要在各需求集之間建立一個光通道，并為其分配一定的波長，使得通過同一條弧上的任何兩個光通道分配不同的波長，記x(R)為所需的最小的波長數(shù)目。令x(G)=minR{x(R)}，則波長分配問題(TheWavelengthAssignmentPr

3、oblem)就是要構造一個路由集和波長分配方案，使其所用的波長數(shù)達到x(G)?？紤]到波長資源的有限性，因此優(yōu)化光通道的路由和波長分配方案成為網(wǎng)絡設計的核心問題。已證實確定x(R)是一個NP一完全問題，但對一些特殊圖如樹、圈，其波長數(shù)目是可確定。 本文主要考慮弧負載指標。首先給出一般圖在點負載指標、最大度、最小度等條件下，弧負載指標的上、下界。接著給出2-連通圖的弧負載指標的一個上界。進一步地，還研究了直徑為2的2-連通圖弧負載指