基于生存性重路由的无线光宽带接入网优化部署方法

摘要

基于生存性重路由的无线光宽带接入网优化部署方法属于通信网络技术领域，尤其涉及一种基于生存性重路由的无线光宽带接入网优化部署方法。本发明提出一种基于生存性重路由的无线光宽带接入网优化部署方法SRRD(Survivable Re-Route Deployment)，用于解决无线路由器的优化布置问题。本发明包括以下步骤：步骤1：将整个网络区域划分成M×M个网格单元，并以每个网格单元的中心作为放置无线路由器的可能位置；步骤2：设R

说明书

技术领域

本发明属于通信网络技术领域，尤其涉及一种基于生存性重路由的无线光 宽带接入网优化部署方法。

背景技术

随着人们生活水平的不断提高，近年来，在IPTV、视频会议等高要求宽带 业务的推动下，宽带接入网络技术正经历迅速的发展。相比于传统的接入网技 术，无线光宽带接入网可以满足更高的带宽要求、获得更灵活的网络控制能力 和更好的服务质量，同时支持新型的多媒体业务，从而能更好的满足接入网络 用户的需求，是一种非常有应用前景的接入网技术。因此对无线光宽带接入网 的研究成为近年来的热点问题。

作为光接入网和无线接入网的折衷方案，无线光宽带接入网有效地实现了 两种接入网技术的优势互补，即利用光接入网的高带宽容量、高稳定性等优势 以及无线接入网的高灵活性、低成本等优势，使用户能在任何时间、任意地点 享受到高质量的宽带接入服务。无线光宽带接入网通常采用“树形-网状” (tree-mesh)结构，即每个区域(segment)由一个树形的无源光网络(后端) 和一个无线网状网(前端)组成。在后端无源光网络和前端无线网状网交汇部 分，光网络单元(Optical Network Unit，ONU)融合了无线网关的功能。所属 不同区域的光线路终端(Optical Line Terminal，OLT)可通过光纤链路互连， 从而构成多区域无线光宽带接入网。用户在访问Internet时，首先将数据分组 发送到所属区域的无线路由器，然后以多跳的方式通过前端的无线网状网到达 无线网关，再经过后端无源光网络的ONU到达OLT，最后进入主干网，从而实现 与Internet的连接。

无线光宽带接入网的网络结构如图1所示，由后端的无源光网络和前端的 无线网状网组成。无源光网络由服务商的OLT，一个光分路器(Splitter)和一 组靠近终端用户的ONU组成。每个OLT通过主干光纤链路连接到光分路器，经 由分支光纤链路驱动多个ONU，每个ONU具有无线网关的功能，并在网络前端部 署无线路由器构建无线网状网，可实现无线接入技术与无源光网络的有效融合。 通过两种接入技术优势互补可有效提高无源光网络宽带接入灵活性。在无线光 宽带接入网中，网络部署问题涉及ONU布置、网络生存性、无线路由器放置等 关键技术。为减小网络部署成本并提高网络的生存能力，在保留原有无源光网 络总体架构的基础上，优化无线路由器的布置位置成为改善网络性能的重要途 径之一。现有无线路由器布置方法大多针对无线网状网络，且对无线光宽带接 入网络的生存性考虑较少，在无线接入跳数及网络覆盖范围等方面考虑不够完 善。因此无法有效应用于基于生存性重路由的无线光宽带接入网优化部署。然 而，无线接入跳数、网络覆盖范围及网络生存性限制是影响用户服务质量及服 务体验的重要因素，也是制约网络可扩展能力的关键条件，在基于生存性重路 由的无线光宽带接入网优化部署问题中具有重要的研究意义。

发明内容

针对现有研究中存在的不足，本发明提出一种基于生存性重路由的无线光 宽带接入网优化部署方法SRRD(Survivable Re-Route Deployment)，用于解 决无线路由器的优化布置问题。

为实现上述目的，本发明采用如下技术方案，本发明包括以下步骤：

步骤1：将整个网络区域划分成M×M个网格单元，并以每个网格单元的中 心作为放置无线路由器的可能位置；

步骤2：设R_x表示当前将要放置的一个无线路由器，在满足每个ONU到其 它一个ONU存在k条节点不相交路径及无线接入跳数约束的条件下，计算出可 以放置无线路由器R_x的所有候选位置，从而确定所有ONU的备用ONU；在候选 位置上放置无线路由器R_x，保证任意ONU能通过k条满足跳数约束且节点不相 交的无线路径接入到其它的一个ONU；

步骤3：按照无线路由器R_x的传输范围，计算放置好这些无线路由器后的 网络覆盖范围；这里的网络覆盖范围是通过用户终端是否在该无线路由器传输 范围内来计算的，即如果在该无线路由器的传输范围内，用户终端数加1；

步骤4：判断是否完成所有N个终端用户的完全覆盖；如果是，转向步骤7， 否则，转向步骤5；

步骤5：从剩余未铺设的无线路由器R_y的所有候选位置中选出网络覆盖范 围最大的一个作为R_y的最佳布置位置，并保证该无线路由器被放置后，在满足 跳数约束的情况下，能够通过一条无线路径以最小跳数与一个ONU相连，保证 该无线路径都放置上无线路由器，并统计所有已放置好的无线路由器覆盖范围， 跳转到步骤4；

步骤6：输出无线路由器各自的布置位置，每个ONU到其备用ONU的无线路 径，以及其他无线路由器到各自相连接的ONU的无线路径。

一种基于生存性重路由的无线光宽带接入网优化部署方法，包括以下步骤：

步骤1：将6km×6km的方形网络区域划分成M×M个网格单元，并以每个网 格单元的中心点作为放置无线路由器的可能位置；

步骤2：对于任意初始化ONU_i到其他ONU_j的最短无线路径跳数 H_i→j＝0；初始化节点不相交路径的条数k＝1；

步骤3：遍历网络中所有未放置无线路由器的网格单元中心点，计算出可以 放置无线路由器R_x的候选位置C_m的集合Φ_x，初始化无线路由器索引号x＝1；若 其中任意一个网格单元中心点C_m满足网络中每个ONU能够找到其备用ONU，且 可通过满足无线路由跳数约束的k条节点不相交路径相连接，那么将C_m作为R_x的一个候选位置，Φ_x←C_m；

步骤4：在集合Φ_x中候选位置C_m上放置无线路由器，并计算出无线路由器R_x所覆盖的用户终端的集合N_m←{N_u|d(L_u,C_m)≤T；u＝1,L,N}，确定被覆盖用户终端 的数目n；

步骤5：判断n＝N是否成立；如果是，说明用户终端已经被完全覆盖，跳转 到步骤9；否则，跳转到步骤6；

步骤6：计算剩余未放置无线路由器的位置集合Φ_y，选取Φ_y中覆盖新用户 终端数目n_y最多的位将无线路由器R_y放置到该位置上；

步骤7：计算R_y到每个ONU(如ONU_w)的最短无线接入跳数据此，决 策出R_y的目的其中

步骤8：在节点R_y及其目的的无线路径都放置上无线路由器，并重新 计算出所有已经放置的无线路由器所覆盖的用户终端的集合N_m，以及被覆盖用 户数目n，跳转到步骤5；

步骤9：输出无线路由器各自的布置位置，每个ONU到其备用ONU的无线路 径，以及其他无线路由器到各自相连接的ONU的无线路径；

m：网格单元编号，m∈{1,2,3,L,M×M}；

C_m：编号为m的网格单元中心点，即无线路由器的放置位置；

x,y：无线路由器编号；

k：节点不相交路径的条数；

R_x：编号分别为x的无线路由器；

ONU编号；

ONU_i：编号为i的ONU；

H_i→j：ONU_i到ONU_j的最短无线路径跳数；

无线路由器R_y到ONU_w的最短无线路径跳数；

Φ_x,Φ_y：放置无线路由器的候选位置集合；

N_m：放置在C_m上的无线路由器所覆盖的用户终端的集合；

T：无线路由器的传输范围；

u：用户终端的编号；

L_u：用户终端u的位置；

N：用户终端的总数；

n：用户终端的个数；

d(L_u,C_m)：位置L_u与位置C_m之间的距离。

作为一种优选方案，本发明各所述无线路由器有相同的传输范围，只有位 于彼此传输范围内的两个无线路由器之间才存在可用的双向无线链路；每个无 线路由器负责聚合来自其覆盖范围内的用户业务，并通过无线多跳路径将业务 传递到其目的ONU；同时，当因分支光纤断裂造成业务传输中断时，需要通过无 线路由器将与该分支光纤相连接的ONU的业务倒换到其他备用ONU上；并且， 保证ONU与其备用ONU之间存在k条满足跳数约束的节点不相交路径，以增强 网络的生存能力；而且，在无线路由器与其目的ONU之间至少存在一条长度小 于H跳的无线路径来实现业务接入，确保无线路由器到ONU的端到端时延要求。

作为另一种优选方案，本发明在所述6km×6km的方形区域内铺设无线光宽 带接入网络的ONU和无线路由器，具有无线网关功能的ONU和无线路由器的传 输范围均设置在1.5km，并在该方形区域内随机放置200个用户终端，每个用户 终端都分别指代一定的用户密度，分别从[0，499]，[500，999]，[1000，1499]， [1500，1999]，[2000，2499]和[2500，2999]中取值；每个ONU到其备用ONU， 以及每个无线路由器到其目的ONU的无线接入跳数不超过H跳。

本发明有益效果。

已知需要布置的ONU的数量及位置，本发明在满足无线接入跳数和网络生 存性限制的条件下，通过优化无线路由器布置位置，最大化无线覆盖范围。

1)本发明将具有无线网关功能的ONU作为接口，在前端建立无线网状网络， 同时考虑网络生存性的关键问题，从而大大提高网络的生存能力及鲁棒性。

2)本发明以最小化无线路由器的数量为目标，考虑网络完全覆盖以及无线 接入跳数的约束，从而降低网络后续建设及部署中的成本。

3)与运算复杂度较高的线性规划ILP方法相比，本发明采用了高效的启发 式方法来获得无线路由器的最佳部署方案，更适用于大规模的网络部署中。

4)本发明具有较好的网络扩展性，在无源光网络原有架构的基础上，仅需 要将部分ONU替换成具有无线网关功能的ONU，从而达到易安装、便于维护、低 成本的效果。

针对光纤不可达的区域，本发明采用具有无线网关功能的ONU，不但可以为 无线终端设备及广大终端用户提供随时随地的宽带接入，而且也为基于无源光 网络的远程监测以及应急通信等应用提供了非常有价值的可行性。

附图说明

下面结合附图和具体实施方式对本发明做进一步说明。本发明保护范围不 仅局限于以下内容的表述。

图1为现有无线光宽带接入网络结构示意图；

图2为本发明中基于生存性重路由的无线光宽带接入网络结构示意图；

图3为本发明中基于生存性重路由的无线光宽带接入网优化部署方法SRRD 流程图；

图4为本发明中SRRD方法在节点不相交路径条数为1且网络完全覆盖情况 下，ONU及无线路由器的放置示意图；

图5为本发明中SRRD方法在节点不相交路径条数为2且网络完全覆盖情况 下，ONU及无线路由器的放置示意图；

图6为本发明中SRRD方法在节点不相交路径条数为1且网络完全覆盖情况 下，不同数目的ONU，所需无线路由器个数对比示意图；

图7为本发明中SRRD方法在节点不相交路径条数为2且网络完全覆盖情况 下，不同数目的ONU，所需无线路由器个数对比示意图。

具体实施方式

如图所示，本发明包括以下步骤：

步骤1：将整个网络区域划分成M×M个网格单元，并以每个网格单元的中 心作为放置无线路由器的可能位置。

步骤2：设R_x表示当前将要放置的一个无线路由器，在满足每个ONU到其 它一个ONU存在k条节点不相交路径及无线接入跳数约束的条件下，计算出可 以放置无线路由器R_x的所有候选位置，从而确定所有ONU的备用ONU。在候选 位置上放置无线路由器R_x，保证任意ONU能通过k条满足跳数约束且节点不相 交的无线路径接入到其它的一个ONU。

步骤3：按照无线路由器R_x的传输范围，计算放置好这些无线路由器后的 网络覆盖范围。这里的网络覆盖范围是通过用户终端是否在该无线路由器传输 范围内来计算的，即如果在该无线路由器的传输范围内，用户终端数加1。

步骤4：判断是否完成所有N个终端用户的完全覆盖。如果是，转向步骤7， 否则，转向步骤5。

步骤5：从剩余未铺设的无线路由器R_y的所有候选位置中选出网络覆盖范 围最大的一个作为R_y的最佳布置位置，并保证该无线路由器被放置后，在满足 跳数约束的情况下，能够通过一条无线路径以最小跳数与一个ONU相连，保证 该无线路径都放置上无线路由器，并统计所有已放置好的无线路由器覆盖范围， 跳转到步骤4。

步骤6：输出无线路由器各自的布置位置，每个ONU到其备用ONU的无线路 径，以及其他无线路由器到各自相连接的ONU的无线路径。

下面结合附图和实施例对本发明的具体实施方式作进一步详细说明。

在本实施例中，所有无线路由器有相同的传输范围，因此只有位于彼此传 输范围内的两个无线路由器之间才存在可用的双向无线链路。每个无线路由器 负责聚合来自其覆盖范围内的用户业务，并通过无线多跳路径将业务传递到其 目的ONU。同时，当因分支光纤断裂造成业务传输中断时，需要通过无线路由器 将与该分支光纤相连接的ONU的业务倒换到其他备用ONU上。并且，保证ONU 与其备用ONU之间存在k条满足跳数约束的节点不相交路径，以增强网络的生 存能力。而且，在无线路由器与其目的ONU之间至少存在一条长度小于H跳的 无线路径来实现业务接入，确保无线路由器到ONU的端到端时延要求，如图2 所示。

本实施例在6km×6km的方形区域内铺设无线光宽带接入网络的ONU和无线 路由器，具有无线网关功能的ONU和无线路由器的传输范围均设置在1.5km，并 在该方形区域内随机放置200个用户终端，为了更好的反映真实场景，每个用 户终端都分别指代一定的用户密度，分别从[0，499]，[500，999]，[1000，1499]， [1500，1999]，[2000，2499]和[2500，2999]中取值。每个ONU到其备用ONU， 以及每个无线路由器到其目的ONU的无线接入跳数不超过H跳。

本实施例中涉及到的已知参数和变量如下：

m：网格单元编号，m∈{1,2,3,L,M×M}

C_m：编号为m的网格单元中心点，即无线路由器的放置位置。

x,y：无线路由器编号。

k：节点不相交路径的条数。

R_x：编号分别为x的无线路由器。

ONU编号。

ONU_i：编号为i的ONU。

H_i→j：ONU_i到ONU_j的最短无线路径跳数。

无线路由器R_y到ONU_w的最短无线路径跳数。

Φ_x,Φ_y：放置无线路由器的候选位置集合。

N_m：放置在C_m上的无线路由器所覆盖的用户终端的集合。

T：无线路由器的传输范围。

u：用户终端的编号。

L_u：用户终端u的位置。

N：用户终端的总数。

n：用户终端的个数。

d(L_u,C_m)：位置L_u与位置C_m之间的距离。

本发明的实施流程描述如图3所示，包括以下步骤：

步骤1：将6km×6km的方形网络区域划分成M×M个网格单元，并以每个网 格单元的中心点作为放置无线路由器的可能位置。

步骤2：对于任意初始化ONU_i到其他ONU_j的最短无线路径跳数 H_i→j＝0；初始化节点不相交路径的条数k＝1。

步骤3：遍历网络中所有未放置无线路由器的网格单元中心点，计算出可以 放置无线路由器R_x的候选位置C_m的集合Φ_x，初始化无线路由器索引号x＝1。目 的是，若其中任意一个网格单元中心点C_m满足网络中每个ONU能够找到其备用 ONU，且可通过满足无线路由跳数约束的k条节点不相交路径相连接，那么将C_m作为R_x的一个候选位置，Φ_x←C_m。

步骤4：在集合Φ_x中候选位置C_m上放置无线路由器，并计算出无线路由器R_x所覆盖的用户终端的集合N_m←{N_u|d(L_u,C_m)≤T；u＝1,L,N}，从而确定被覆盖用户 终端的数目n。

步骤5：判断n＝N是否成立。如果是，说明用户终端已经被完全覆盖，跳转 到步骤9；否则，跳转到步骤6。

步骤6：计算剩余未放置无线路由器的位置集合Φ_y，选取Φ_y中覆盖新用户 终端数目n_y最多的位置将无线路由器R_y放置到该位置上。

步骤7：计算R_y到每个ONU(如ONU_w)的最短无线接入跳数据此，决 策出R_y的目的其中

步骤8：在节点R_y及其目的的无线路径都放置上无线路由器，并重新 计算出所有已经放置的无线路由器所覆盖的用户终端的集合N_m，以及被覆盖用 户数目n，跳转到步骤5。

步骤9：输出无线路由器各自的布置位置，每个ONU到其备用ONU的无线路 径，以及其他无线路由器到各自相连接的ONU的无线路径。

根据上面的实施例，对本发明提出的SRRD方法在1)节点不相交路径条数 为1且网络完全覆盖；2)节点不相交路径条数为2且网络完全覆盖，这两种情 况下ONU和无线路由器的放置进行分析，并且在SRRD与ILP和随机放置方法下， 不同数目的ONU所需无线路由器的个数进行对比与分析。

图4为SRRD方法在节点不相交路径条数为1且网络完全覆盖情况下ONU及 无线路由器的放置示意图。为简化网络覆盖范围的计算并便于观察，将方形网 络区域划分为6×6个网格单元。ONU的个数设置为4个，在满足节点不相交路 径条数为1且网络完全覆盖情况下，无线路由器所需要的个数为29个。图5为 相同的网络场景环境下，SRRD方法在节点不相交路径条数为2且网络完全覆盖 情况下ONU及无线路由器的放置示意图。此时，无线路由器的个数为30个。同 时，对比两图可以看出，无线路由器的铺设以及所经过的无线路径都不同，这 与节点不相交路径条数约束有关。

图6为SRRD方法在节点不相交路径条数为1且网络完全覆盖情况下，不同 数目的ONU，所需无线路由器个数对比示意图。为了便于研究ONU的数目对无线 路由器个数的影响，将该方形网络区域划分为10×10个网格单元。由图中可以 看出，在满足节点不相交路径条数为1且网络完全覆盖情况下，SRRD方法获得 的结果要远远优于随机放置的结果，并趋近于ILP方法所得的结果。图7为SRRD 方法在节点不相交路径条数为2且网络完全覆盖情况下，不同数目的ONU，所需 无线路由器个数对比示意图。仿真曲线的变化趋势与图6相似，不同之处是由 于节点不相交路径条数约束所致。节点不相交路径的条数越多，相同数目的ONU 所需的无线路由器个数就越多，网络的生存能力就越强。

综上所述，本发明提出的SRRD方法能在满足无线路由器的接入跳数限制， 以及网络生存性限制情况下，实现网络的完全覆盖。不仅能减小无线光宽带接 入网的成本，还能实现光纤不可达区域随时随地的宽带接入。因此能在保证业 务正常进行的情况下改善网络可扩展能力。

可以理解的是，以上关于本发明的具体描述，仅用于说明本发明而并非受 限于本发明实施例所描述的技术方案，本领域的普通技术人员应当理解，仍然 可以对本发明进行修改或等同替换，以达到相同的技术效果；只要满足使用需 要，都在本发明的保护范围之内。