光纖網(wǎng)絡(luò)的弧負(fù)載指標(biāo)及波長分配問題.pdf

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

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

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