[go: up one dir, main page]

CN110798841B - 多跳无线网络部署方法、网络能力确定方法和装置 - Google Patents

多跳无线网络部署方法、网络能力确定方法和装置 Download PDF

Info

Publication number
CN110798841B
CN110798841B CN201810869586.3A CN201810869586A CN110798841B CN 110798841 B CN110798841 B CN 110798841B CN 201810869586 A CN201810869586 A CN 201810869586A CN 110798841 B CN110798841 B CN 110798841B
Authority
CN
China
Prior art keywords
deployment
deployment scheme
link
generation
scheme
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201810869586.3A
Other languages
English (en)
Other versions
CN110798841A (zh
Inventor
吴杰
李红春
徐怡
田军
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to CN201810869586.3A priority Critical patent/CN110798841B/zh
Publication of CN110798841A publication Critical patent/CN110798841A/zh
Application granted granted Critical
Publication of CN110798841B publication Critical patent/CN110798841B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W16/00—Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
    • H04W16/18—Network planning tools
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/12—Computing arrangements based on biological models using genetic models
    • G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/04—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources
    • H04W40/06—Communication route or path selection, e.g. power-based or shortest path routing based on wireless node resources based on characteristics of available antennas
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/12—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/12—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality
    • H04W40/16—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality based on interference
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/121—Shortest path evaluation by minimising delays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/122—Shortest path evaluation by minimising distances, e.g. by selecting a route with minimum of number of hops
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/124—Shortest path evaluation using a combination of metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/125—Shortest path evaluation based on throughput or bandwidth
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/126—Shortest path evaluation minimising geographical or physical path length

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Biophysics (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • Theoretical Computer Science (AREA)
  • Artificial Intelligence (AREA)
  • Molecular Biology (AREA)
  • Biomedical Technology (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Genetics & Genomics (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Physiology (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

本发明实施例提供一种多跳无线网络部署、网络能力确定方法和装置，其中，该多跳无线网络部署装置包括：第一处理单元，其用于使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，所述部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息；第一确定单元，其用于在满足预定条件时，将所述第一处理单元生成的所述第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。通过本实施例的上述装置，能够优化无线网络部署方案，提高部署方案的网络性能。

Description

多跳无线网络部署方法、网络能力确定方法和装置
技术领域
本发明涉及通信技术领域，尤其涉及一种多跳无线网络部署、网络能力确定方法和装置。
背景技术
无线通信技术的发展为用户随时随地接入网络带来了极大的便利，在多跳无线网络中，源节点到目的节点之间的典型路径是由多跳组成的，多跳无线网络中的每个节点既可以产生或接收数据分组，也可以作为转发节点对来自其他节点的数据分组进行转发。在现有的无线网络中，无线点对点(Ad Hoc)网络，无线传感器网络以及无线网状(Mesh)网络均属于多跳无线网。
在多跳无线网中，网络性能(例如干扰、吞吐量、端到端时延等)的优劣与节点位置的选取和/或节点接口的配置紧密相关，如果节点位置的选取和/或节点接口的配置不得当，会造成多跳无线网络性能较差，且增加建设成本。
应该注意，上面对技术背景的介绍只是为了方便对本发明的技术方案进行清楚、完整的说明，并方便本领域技术人员的理解而阐述的。不能仅仅因为这些方案在本发明的背景技术部分进行了阐述而认为上述技术方案为本领域技术人员所公知。
发明内容
全向天线能够将能量均匀地分布在各方向上不同，定向天线是将能量集中在某一特定方向，因此，定向天线比全向天线具有更远的传输距离，由于多跳无线网络的部署目标是提高网络覆盖范围、降低干扰、提高空间利用率，因此，如果在多跳无线网络中的节点上配置定向天线，即可以提高无线多跳网络的覆盖范围、减少多跳无线网络的跳数
在现有技术中，在进行网络部署时，通常是在节点配置全向天线的前提下，仅考虑节点位置选取以及节点数量的优化，但在有节点配置了定向天线的情况下，目前，还没有有效的方法对该节点上的定向天线的参数配置进行优化。
本发明实施例提出了一种多跳无线网络部署方法和装置，考虑节点位置、路径选择和路径上的节点的天线配置，从而能够优化无线网络部署方案，提高部署方案的网络性能。
另外，目前的网络性能评价方法仅仅考虑了一些单一的性能指标来评价网络性能，例如网络负载、时延、吞吐量等，但由于在多跳无线网络中，可能存在多链路、多路径，不同链路、路径之间可能存在干扰，因此，现有技术中的网络性能评价方法无法准确的评价网络性能。
本发明实施例提出了一种网络能力确定方法和装置，考虑邻居节点之间的相互影响，根据网络中数据传输已占用容量与剩余容量的关系确定网络能力，将该网络能力作为评价网络性能的指标，从而能够更加准确的评价多跳无线网络的网络性能。
本发明实施例的上述目的是通过如下技术方案实现的：
根据本发明实施例的第一个方面，提供了一种多跳无线网络部署装置，该装置包括：
第一处理单元，其用于使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，所述部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息，i为大于等于零的整数；
第一确定单元，其用于在满足预定条件时，将所述第一处理单元生成的所述第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
根据本发明实施例的第二个方面，提供了一种网络能力确定装置，该装置包括：
第三确定单元，其用于根据当前传输的数据量以及网络中传输潜力最小的链路能够传输的数据量确定所述网络能力；其中，所述链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
本发明实施例的有益效果在于，在进行多跳无线网络部署时，在进行网络部署时，考虑节点位置、路径选择和路径上的节点的天线配置，从而能够优化无线网络部署方案，提高部署方案的网络性能。
本发明实施例的有益效果在于，考虑邻居节点之间的相互影响，根据网络中数据传输已占用容量与剩余容量的关系确定网络能力，将该网络能力作为评价网络性能的指标，从而能够更加准确的评价多跳无线网络的网络性能。
参照后文的说明和附图，详细公开了本发明的特定实施方式，指明了本发明的原理可以被采用的方式。应该理解，本发明的实施方式在范围上并不因而受到限制。在所附权利要求的精神和条款的范围内，本发明的实施方式包括许多改变、修改和等同。
针对一种实施方式描述和/或示出的特征可以以相同或类似的方式在一个或更多个其它实施方式中使用，与其它实施方式中的特征相组合，或替代其它实施方式中的特征。
应该强调，术语“包括/包含”在本文使用时指特征、整件、步骤或组件的存在，但并不排除一个或更多个其它特征、整件、步骤或组件的存在或附加。
附图说明
参照以下的附图可以更好地理解本发明的很多方面。附图中的部件不是成比例绘制的，而只是为了示出本发明的原理。为了便于示出和描述本发明的一些部分，附图中对应部分可能被放大或缩小。在本发明的一个附图或一种实施方式中描述的元素和特征可以与一个或更多个其它附图或实施方式中示出的元素和特征相结合。此外，在附图中，类似的标号表示几个附图中对应的部件，并可用于指示多于一种实施方式中使用的对应部件。
在附图中：
图1是定向天线覆盖范围示意图；
图2是定向天线通信场景示意图；
图3是本实施例1中多跳无线网络部署方法的流程图；
图4A是本实施例1中待部署区域离散化的示意图；
图4B是本实施例1中偏离度示意图；
图5是本实施例1中步骤301的方法的流程图；
图6是本实施例1中适应度计算方法流程图；
图7是本实施例1中适应度计算示意图；
图8是本实施例2中多跳无线网络部署方法的流程图；
图9是本实施例3中网络能力确定方法流程图；
图10是本实施例4中多跳无线网络部署装置的示意图；
图11是本实施例4中第一处理单元的示意图；
图12是本实施例4中多跳无线网络部署装置的硬件构成示意图。
图13是本实施例5中网络能力确定装置的示意图；
图14是本实施例5中网络能力确定装置的硬件构成示意图。
具体实施方式
参照附图，通过下面的说明书，本发明实施例的前述以及其它特征将变得明显。这些实施方式只是示例性的，不是对本发明的限制。为了使本领域的技术人员能够容易地理解本发明的原理和实施方式，本发明实施例以无线传感器网络为例进行说明，但可以理解，本发明实施例并不限于无线传感器网络，例如，本发明实施例提供的方法和装置也适用于其它需要进行多跳无线网络部署的网络。
以下为方便理解，对遗传算法以及定向天线进行简要说明。
遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，通过模拟生物进化过程来完成优化搜索，近年来，遗传算法广泛的应用于无线网络部署领域。使用遗传算法计算无线网络部署方案主要包括以下步骤：首先，建立模型，将部署方案编码为一段染色体，每一个染色体又由若干个基因位(候选位置)组成，为了便于实现遗传算法的处理过程，需要对每一代部署方案集中的部署方案进行编码；其次，选择并应用适应性函数决定染色体的优胜劣汰，然后染色体之间互相结合，交叉产生新一代染色体，最后采用变异方式得到新的部署方案，循环进行此过程直到计算出较优的部署方案。
图1是节点配置了定向天线后的覆盖范围示意图，如图1所示，定向天线将能量集中在角度θ内，该角度θ称为该天线的波束宽度，半径R2的扇形区域称为该天线的信号覆盖范围，该半径R2为该天线的传输距离，该定向天线的方向角所指的方向(图1箭头所示)，称为该天线的方向；当节点配置了定向天线时，如果要求节点间可以通信，则不仅需要节点间距离小于R2，还需要两个节点同时处于对方的覆盖范围之内，图2是定向天线通信场景示意图，如图2所示，配置了如图1所示的定向天线的节点A和B处于对方的半径为R2的扇形区域内，即覆盖范围内。
下面参照附图对本发明的具体实施方式进行说明。
实施例1
本实施例1提供一种多跳无线网络部署方法；图3是该多跳无线网络部署方法的流程图，如图3所示，该方法包括：
步骤301，使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；
步骤302，在满足预定条件时，将生成的该第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
在本实施例中，为了获得较优的部署方案，不仅需要考虑节点的位置部署，还需要考虑多跳无线网络中路径的选择以及各个路径上的节点配置的天线信息，因此，在本实施例中，该部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息，i为大于等于零的整数。
通过本实施例的上述方法，在进行多跳无线网络部署时，考虑节点位置、路径选择和路径上的节点的天线配置，从而能够优化无线网络部署方案，提高部署方案的网络性能。
在本实施例中，该至少一个源节点到至少一个目的节点之间的一条以上路径可以使用路径依次经过的节点(例如节点标识)表示，或者为了方便进行遗传算法的处理，可以将每个部署方案(每个个体)使用路径分配表(Path_Tab)表示(编码)，该路径分配表的每一行表示一条从源节点到目的节点的路径，行数表示源节点到目的节点的路径数，该路径分配表的每一列表示路径上节点的跳数，列数表示所有节点位置的数目；该路径分配表分为第一部分和第二部分，其中，该第一部分表示每条路径经过的节点标识(ID)，第二部分表示无节点，例如，使用数字“0”表示(也可以用其他值表示，本实施例并不以此作为限制)，即该表格中每一行的第一个非零值表示源节点ID，最后一个非零值表示目的节点ID，零值表示未经过的节点，或者说无节点，每一行第一个0的出现表示路径结束了，每一行的非零值依次连接构成一条由源节点至目的节点的路径，下表1是路径分配表一示意：
表1路径分配表(Path_Tab)
1 2 3 6 9 0 0 0 0
1 4 7 8 9 0 0 0 0
5 8 9 0 0 0 0 0 0
5 6 9 0 0 0 0 0 0
如表1所示，该部署方案的节点为9个，共存在4条由源节点至目的节点的路径，分别为1-2-3-6-9(5跳路径)，1-4-7-8-9(5跳路径)，5-8-9(3跳路径)，5-6-9(3跳路径)，其中，0表示一条路径在对应的跳数位置未经过节点。
在本实施例中，路径分配表还可以表示为其他形式，只有能够体现相应的参数即可。
在本实施例中，该各个路径上的节点配置的天线信息可以包括天线的波束宽度和/或天线的方向信息，该方向信息包括上行方向信息和/或下行方向信息，该上行方向信息和/或下行方向信息为上行方向和/或下行方向与链路连线的偏离度，该上下行方向可以用方向角所指的方向表示。为了方便进行遗传算法的处理，可以将每个部署方案(每个个体)使用天线分配表表示(编码)，例如，该天线信息是上行方向信息和下行方向信息时，该天线分配表的每一行表示一条从源节点到目的节点的路径，与上表1对应，行数表示源节点到目的节点的路径数，每一列表示路径上相邻节点间的链路，列数表示路径上的链路数；表中每一行每一列对应的值用实数对(k1，k2)表示，k1和k2分别表示上行方向角和下行方向角与链路连线的偏离度，该偏离度与实际的偏离角度有对应关系，例如偏离角度为0～10°时，该偏离度为1，偏离角度为10～30°时，该偏离度为2，偏离角度为-10～-30°时，该偏离度为-2，以此类推，此处不再一一举例，该正负值表示方向角与链路连线的偏离度在该连线的两侧相反方向，下表2是天线分配表二示意：
表2天线分配表
(-1,2) (0,-2) (1,3) (2,-1) Inf Inf Inf Inf Inf
(2,0) (-3,2) (0,1) (3,0) Inf Inf Inf Inf Inf
(-3,3) (2,1) Inf Inf Inf Inf Inf Inf Inf
(2,-3) (-1,-3) Inf Inf Inf Inf Inf Inf Inf
如表2所示，第一行第一列的实数对(-1,2)，图4B是该偏离度示意图，如图4B所示，实数对(-1,2)表示表1中的路径1-2-3-6-9中链路1-2的上行方向角与链路1-2的连线的偏离度是-1(如图4B向下偏离)，链路1-2的下行方向角与链路1-2的连线的偏离度是2(如图4B向上偏离)，inf表示无链路，也可以用其他值表示，本实施例并不以此作为限制。
需要说明的是，以上以实数对(k1，k2)作为示例说明，但本实施例并不以此作为限制，该偏离度还可以直接用该偏离角度或其他方式表示，另外，该天线分配表可以仅包含k1或仅包含k2；或天线分配表的每一行每一列可以与表1对应，每一行每一列的值分别表示表示表1路径每个非0节点的天线的波束宽度k3，下表3是天线分配表三示意：即天线信息包含k1，k2，k3中的至少一个，此处不再一一举例。
表3天线分配表
20° 30° 10° 30° 20° Inf Inf Inf Inf
20° 30° 10° 10° 20° Inf Inf Inf Inf
20° 30° 20° Inf Inf Inf Inf Inf Inf
20° 30° 20° Inf Inf Inf Inf Inf Inf
在本实施例中，可选的，该每个部署方案还可以包括该路径上各个链路的信道信息，为了方便进行遗传算法的处理，可以将每个部署方案(每个个体)使用信道分配表(CA_Tab)表示(编码)，该信道分配表的行数和列数都等于节点数，行号和列号分别对应节点标识(ID)(其中，行号和列号可以包含在该信道分配表中，也可以不包含在该表中)，该信道分配表中的各个项表示每两个节点之间的链路使用的信道号(ID)；节点之间未使用信道，或者节点之间不存在链路，无需传输数据，未分配信道，可以用0表示，也可以用其他值表示，本实施例并不以此作为限制，下表4是信道分配表一示意：
表4信道分配表(CA_Tab)
1 2 3 4 5 6 7 8 9
1 0 3 2 3 3 2 1 3 2
2 0 0 1 3 2 3 1 1 1
3 0 0 0 1 2 3 2 2 3
4 0 0 0 0 2 2 1 2 1
5 0 0 0 0 0 1 3 2 1
6 0 0 0 0 0 0 3 3 2
7 0 0 0 0 0 0 0 2 3
8 0 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 0 0 0
如表4所示，该部署方案的节点为9个，其中，链路1-2使用的信道号为3，链路1-3使用的信道号为2，链路2-3使用的信道号为1，此处不再一一举例，0表示节点9和节点1之间不存在链路，或者说节点9和1之间未分配信道。
在本实施例中，信道分配表还可以表示为其他形式，只有能够体现相应的参数即可，例如该信道分配表的行数等于源节点至目的节点的路径数，列号表示一条路径上的链路序号，该信道分配表中的各个项表示路径上每两个节点之间的链路使用的信道号(ID)；节点之间未使用信道，或者节点之间不存在链路，无需传输数据，未分配信道，可以用0表示，也可以用其他值表示，本实施例并不以此作为限制，下表5是信道分配表一示意：
表5信道分配表(CA_Tab)
1 2 3 1 0 0 0 0 0
1 3 2 2 0 0 0 0 0
3 1 0 0 0 0 0 0 0
2 3 0 0 0 0 0 0 0
如表5所示，表5第一行的非零值分别为1,2,3,1，即表示路径分配表1中第一行所表示的路径1→2→3→6→9的各链路1→2，2→3，3→6，6→9的信道号为1,2,3,1。
由此，在进行多跳无线网络部署时，除了节点位置、路径选择和路径上的节点的天线配置，还可以考虑信道分配，从而能够优化无线网络部署方案，进一步提高部署方案的网络性能。
在本实施例中，在步骤301前，该方法还包括：先将待部署区域离散化为若干个候选节点位置，并依次对每个节点位置进行编号，得到节点ID；下面结合图4A对本实施例中的离散化方法进行说明。
图4A是本实施例中待部署区域离散化的示意图；如图4A所示，根据每一个节点的通信半径，源节点位置以及目的节点位置，将该待部署区域离散化为N个点，每一个点代表一个候选节点位置，并按顺序将每个节点(候选节点、源节点、目的节点)进行编号为1～8，其中，可以均匀的离散化，也可以非均匀的离散化，此处不再一一举例，其中，候选节点位置包括已部署节点位置以及未部署节点位置。
在本实施例中，在步骤301～302中，该第i代部署方案集可为初始部署方案集，在i取值为零时，该初始部署方案集为第0代部署方案集。其中，使用本实施例的上述编码方式，根据预定路由算法生成第0代部署方案集中的部署方案，然后使用遗传算法，进行相应的迭代，生成最终的部署方案集。
在本实施例中，该预定路由算法可以是Dijkstra算法和Bellman–Ford算法，例如，根据多跳无线网络中的源节点、候选节点位置以及目的节点，使用Dijkstra算法计算从源节点到目的节点的最短路径，将得到的至少一条最短路径表示为路径分配表的形式，作为一个部署方案，依次生成多个部署方案，以获得初始部署方案集。
例如，在获得该初始部署方案集后，可基于遗传算法对第0代部署方案集进行处理，以获得第i+1代(第1代)部署方案集。其中基于遗传算法对第0代部署方案集进行处理主要包括：对第0代部署方案集进行包括选择、交叉、变异的处理，在满足预定条件时，将该第1代种群或第1代部署方案集作为最终的部署方案集；否则针对生成的该第1代部署方案集，利用遗传算法对该第1代部署方案进行处理，即相当于i等于1，重复步骤301中的选择、交叉、变异的处理，以此类推，直至获得最终的部署方案，以下对上述多跳无线网络部署方法进行说明。
在本实施例中，还提出了一种与上述个体编码方式相匹配的改进后的遗传算法，主要涉及遗传算法中的选择、交叉、变异处理，以便获得优化后的部署方案集。
图5是本实施例中步骤301的实施方式流程图。如图5所示，步骤501包括：
步骤501，计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数，根据每个部署方案的至少两个目标函数，计算第i代路由节点部署方案集中的每个部署方案的适应度函数，选择满足第一预定条件的部署方案得到第一部署方案集；其中，该适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比；
步骤502，从该第一部署方案集中，选定第二预定数量(根据需要确定，本实施例并不以此作为限制)组的部署方案，其中每组部署方案包含两个部署方案，将该每组部署方案中的两个部署方案进行交叉处理；
步骤503，从对该第二预定数量组的部署方案进行互换处理后的第一部署方案集中选定第三预定数量(根据需要确定，本实施例并不以此作为限制)的部署方案，得到第二部署方案集，对第二部署方案集中的部署方案进行变异处理，以得到该第i+1代部署方案集。
在本实施例中，步骤501相当于遗传算法中的选择过程，在步骤501中，该至少两个目标函数包括表示网络能力的函数，以及表示网络成本的函数(例如计算吞吐量、时延、速率、成本等性能指标)，该吞吐量、时延、速率的计算方式可以参考现有技术，网络成本可以根据节点数或节点数以及每个节点的接口数确定，本实施例并不以此作为限制。该第i-1代部署方案集中帕累托解(非支配解)的具体含义可以参考现有技术，此处不再赘述。该适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比，其可以用于评价每个部署方案的优劣程度，通过该适应度函数可以提高遗传算法的收敛速度以及选择较优的部署方案。
图6是该适应度计算方法示意图，如图6所示，该方法包括：
步骤601，将至少两个(m个)目标函数进行归一化处理；
步骤602，将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据该至少两个目标函数建立的m维空间坐标系中；
步骤603，在该坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；
步骤604，选择该距离中的最小距离；
步骤605，将该最小距离的倒数作为该适应度函数。
在本实施例中，为了说明方便，以下以m＝2为例说明，但本实施例并不以此作为限制，图7是该适应度计算示意图，如图7所示，在步骤601中，将各个目标函数进行归一化处理后，建立二维坐标系，横坐标表示目标函数1，纵坐标表示目标函数2，在步骤602中，根据各个部署方案计算的目标函数1和目标函数2，将第i代部署方案集中的部署方案(a)以及第i-1代部署方案集中帕累托解(1～6)映射到上述二维坐标系中；在步骤603中，计算a与帕累托解1～6的欧式距离Dc，在步骤604～605中，选择最小欧式距离Dc为a与2的距离Dc2，将Dc2的倒数作为该适应度函数，即表示第i代部署方案集中的部署方案与第i-1代部署方案集中每个帕累托解的距离的最小值越小，其适应度越大，即其被选择(保留)至第i+1代的概率也越大。
需要说明的是，以上仅以最小距离的倒数作为该适应度函数为例说明，但本实施例并不以此作为限制，只要该适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比即可。
在本实施例中，为了进一步加快遗传算法搜索最优解的速度，在步骤501中，可以选择满足第一预定条件的部署方案(精英解)得到第一部署方案集；该第一预定条件可以是：
1)将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量个(m1个)部署方案；例如，可以选择N个区间中每个区间中目标函数最优的个(n1个)部署方案，得到该m1个部署方案，如果某区间内没有对应目标函数值的部署方案，可以不选择，和/或，
2)选择适应度函数最大的第二预定数量(m2)个部署方案；和/或，
3)选择目标函数中至少一个目标函数是最优值(最优值可以是最大值或最小值，例如，成本越小越优，传输速率越大越优)的第三预定数量个(m3个)部署方案(例如附图7中的部署方案b和/或c)。
在本实施例中，m1，m2，m2为正整数，在步骤501中，可以选择m1，m2，m3中的至少一个，得到该第一部署方案集。
在本实施例中，步骤502相当于遗传算法中的交叉过程，步骤503相当于遗传算法中的变异过程，以下通过举例具体说明。
在步骤502中，将该两个部署方案中相同源节点和目的节点的路径进行交换，且交换后的部署方案中，不存在重复的路径，例如，在部署方案利用路径分配表表示时，可以将相同源节点和目的节点的路径所在的行互换，例如，该两个部署方案中的路径分配表如下表6和7所示：
表6
1 2 3 6 9 0 0 0 0
1 4 7 8 9 0 0 0 0
5 8 9 0 0 0 0 0 0
5 6 9 0 0 0 0 0 0
表7
1 2 3 6 9 0 0 0 0
1 2 5 8 9 0 0 0 0
5 8 9 0 0 0 0 0 0
5 6 9 0 0 0 0 0 0
表6和7中相同源节点和目的节点的路径(且不重复)分别为1-4-7-8-9以及1-2-5-8-9，将上述两条路径互换，得到如下表8和9，交换后的表8和9中不存在重复的路径。
表8
1 2 3 6 9 0 0 0 0
1 2 5 8 9 0 0 0 0
5 8 9 0 0 0 0 0 0
5 6 9 0 0 0 0 0 0
表9
1 2 3 6 9 0 0 0 0
1 4 7 8 9 0 0 0 0
5 8 9 0 0 0 0 0 0
5 6 9 0 0 0 0 0 0
在本实施例中，由于天线分配表以及信道分配表都与该路径分配表中的节点、链路对应，因此，天线分配表以及信道分配表的交叉处理与该路径分配表的交叉处理一致，例如将天线分配表中路径1-4-7-8-9以及1-2-5-8-9所在的行的天线信息交换，在信道分配表中，将路径1-4-7-8-9以及1-2-5-8-9所在的行的信道号交换
在步骤503中，可以选择一条路径上的一个节点，利用预定的路由算法生成该选择的节点至目的节点的第一路径，或源节点至该节点的第二路径，使用该第一路径替换原有的该节点至目的节点的路径，或使用该第二路径替换该原有的源节点至该节点的路径，本实施例并不以此作为限制，变异之后的部署方案中不存在重复路径。
在本实施例中，由于天线分配表以及信道分配表都与该路径分配表中的节点、链路对应，因此，天线分配表以及信道分配表的变异处理与该路径分配表的变异处理对应。以下举例说明。
例如，针对路径1→2→3→6→9，其各链路1→2，2→3，3→6，6→9的天线信息是(2,0)，(-3,2)，(0,1)，(3,0)，各链路1→2，2→3，3→6，6→9的信道号为1,2,3,1，在变异处理时，选择节点3，根据路由算法生成节点1至节点3的路径可以是1→5→4→3，即将1→5→4→3替换原有的1→2→3，变异后的路径为1→5→4→3→6→9，由于增加了新的链路1→5，5→4，4→3，对应的天线信息也要对应的进行变异，但该变异可以是随机的，或者查表得到现有的，例如现有表中也有1→5链路的天线信息是(2,1)，随机生成链路5→4，4→3的天线信息(2,0)，(3,1)，即变异后的天线信息为(2,1)，(2,0)，(3,1)，(0,1)，(3,0)；另外由于增加了新的链路1→5，5→4，4→3，可选的，对应的信道信息也要对应的进行变异，但该变异可以是随机的，或者查表得到现有的，例如现有表中也有1→5链路的信道是5，随机生成链路5→4，4→3的信道1,3，即变异后的信道号为5,1,3,3,1.
以上仅为示例性说明，但该变异的实施方式不限于此，例如，在步骤503中，也可以不变异该路径，仅变异天线信息或信道号，例如针对路径1→2→3→6→9，其各链路1→2，2→3，3→6，6→9的天线信息是(2,0)，(-3,2)，(0,1)，(3,0)，各链路1→2，2→3，3→6，6→9的信道号为1,2,3,1，在变异时，不变异路径1→2→3→6→9，但变异链路1→2(任选一个或多个链路)的天线信息或信道号，将(2,0)随机变异为(2,1)，或者将信道号1随机变异为2等，此处不再一一举例。
在本实施例中，上述步骤503中进行变异的部署方案可以是经过步骤502中交叉后的部署方案，也可以是第一部署方案集中未参与交叉过程的部署方案，本实施例并不以此作为限制，该变异的程度根据变异率确定，变异率越大，变异的内容越多，该变异率的具体实施方式可以参考现有技术，此处不再赘述。
在本实施例步骤302中，该预定条件可以是i+1等于预设的第一阈值，或者是i+1代部署方案集中连续m代部署方案集中的每个部署方案都相同，其中，m为预先设定的第二阈值，则在满足i+1等于预设的第一阈值，或者i+1代部署方案集中连续m代部署方案集中的每个部署方案都相同时，将该第i+1代部署方案集确定为最终的部署方案集。在不满足该预定条件时，针对该第i+1代部署方案集进行处理，直至获得最终的部署方案集；例如，当该第一阈值设为100时，如果i+1＝100，则将得到的第i+1代部署方案集确定为最终的部署方案集；或者当第二阈值设为5时，如果连续5代部署方案集中的每个部署方案都相同，即第i-3、i-2、i-1、i、i+1代部署方案集中的每个部署方案都相同，将得到的第i+1代方案集确定为最终的部署方案集。
在本实施例步骤302中，该预定条件还可以是部署方案集中的部署方案满足网络能力大于第三阈值，在满足该预定条件时，将该第i+1代部署方案集确定为最终的部署方案集。在不满足该预定条件时，针对该第i+1代部署方案集进行处理，该网络能力的确定方式如实施例3所述，此处不再赘述。
通过本实施例的上述方法，在进行多跳无线网络部署时，考虑节点位置、路径选择和路径上的节点的天线配置，从而能够优化无线网络部署方案，提高部署方案的网络性能。
实施例2
本实施例2提供一种多跳无线网络部署方法，图8是本实施例中多跳无线网络部署方法流程图，如图8所示，该方法包括：
步骤801，将待部署区域离散化，生成候选节点位置；依次对各节点进行编号；
步骤802，生成初始部署方案集，将当前的初始部署方案集设为第i代，其中，i＝0；
在本实施例中，使用上述实施例1中的编码方式对初始部署方案集中的每个部署方案进行编码，此处不再重复。
步骤803，从当前第i代部署方案集中选择第一预定数量的部署方案，得到第一部署方案集；
步骤804，从该第一部署方案集中，选定第二预定数量组的部署方案，其中每组部署方案包含两个部署方案，将该每组部署方案中的两个部署方案进行交叉处理；
步骤805，从对该第二预定数量组的部署方案进行互换处理后的第一部署方案集中选定第三预定数量的部署方案，得到第二部署方案集，对第二部署方案集中的部署方案进行变异处理，以得到该第i+1代部署方案集；
其中，步骤803～805的具体实施方式与实施例1中的步骤301～303相同，此处不再重复；
步骤806，判断是否满足预定条件，在判断结果为是时，执行步骤807，否则执行步骤808；其中，预定条件可参照上述步骤302的实施方式，此处不再赘述。
步骤807，将i+1赋予i，并返回步骤803；
步骤808，将第i+1代部署方案集确定为最终的部署方案集。
通过本实施例的上述方法，在进行多跳无线网络部署时，考虑信道分配，从而能够优化无线网络部署方案，提高部署方案的网络性能。
实施例3
本实施例3提供一种网络能力确定方法，图9是本实施例中网络能力确定方法流程图，如图9所示，该方法包括：
步骤901，根据当前传输的数据量以及网络中传输潜力最小的链路能够传输的数据量确定该网络能力；其中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
在本实施例中，该网络能力能够作为评价网络性能的指标，在步骤901中，可以以网络中链路的传输潜力来确定网络能力，该传输潜力表示链路剩余带宽还可以支持传输的数据量(负载)，例如，链路剩余带宽还可以支持传输的数据量越大，表示链路传输潜力越大，即网络能力越强。
在本实施例中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定，该剩余容量(Mbps)表示单位时间内还可以传输的数据量，该已占用容量(Mbps)表示单位时间内已经传输的数据量；其中，该已占用容量等于数据传输占用的容量与干扰传输占用的容量和，该干扰传输占用的容量表示当前传输数据的链路的容量中被干扰链路占用的容量；该链路的传输潜力等于该链路的剩余容量与该已占用容量的比值，即表示链路的剩余容量还可以支持的现有负载(已占用容量)的倍数，即源(当前传输)数据量可以提高的倍数。该倍数越多，表示网络能力越强。
以下说明如何计算该干扰传输占用的容量。
在计算链路i的传输潜力时，确定在链路i的干扰范围内的链路j，Tj表示干扰链路j在链路i的干扰范围内对时间的占用量(％)，Ci表示链路i单位时间内的信道容量，Tj·Ci表示链路i的容量中被干扰链路j占用的容量，在有n个干扰链路j时，该干扰传输占用的容量为
Figure BDA0001751796460000151
其中，可以通过设定第一阈值Q确定在链路i的干扰范围内的链路j，计算链路i与其他链路的距离，将距离小于Q的链路确定为干扰范围内的链路j，其中，该第一阈值Q可以根据干扰半径、节点通信半径确定，本实施例并不以此作为限制；链路间距离等于不同链路中的距离最小的两个节点之间的距离。其中，Tj＝qj/Cj·CHSij，在链路j单位时间内需要传输的数据量为qj，Cj表示链路j单位时间内的信道容量，CHSij为链路i和链路j所用信道之间的信道分离程度，该信道分离度用于表示链路间所使用的信道间存在干扰的程度，其中，干扰越大，信道分离度越大，例如，该信道分离度的取值为0～1，下表10是信道分离度与干扰对应关系(以802.11b为例)。
表10
信道号 1 2 3 4 5 6 7 8 9 10 11
1 1 0.8 0.6 0.4 0.2 0 0 0 0 0 0
2 0.8 1 0.8 0.6 0.4 0.2 0 0 0 0 0
3 0.6 0.8 1 0.8 0.6 0.4 0.2 0 0 0 0
4 0.4 0.6 0.8 1 0.8 0.6 0.4 0.2 0 0 0
5 0.2 0.4 0.6 0.8 1 0.8 0.6 0.4 0.2 0 0
6 0 0.2 0.4 0.6 0.8 1 0.8 0.6 0.4 0.2 0
7 0 0 0.2 0.4 0.6 0.8 1 0.8 0.6 0.4 0.2
8 0 0 0 0.2 0.4 0.6 0.8 1 0.8 0.6 0.4
9 0 0 0 0 0.2 0.4 0.6 0.8 1 0.8 0.6
10 0 0 0 0 0 0.2 0.4 0.6 0.8 1 0.8
11 0 0 0 0 0 0 0.2 0.4 0.6 0.8 1
如表10所示，该表10的行和列分别表示链路i和链路j使用的信道号，例如，当链路i使用的信道与链路j使用的信道相同时，信道分离度为1，即干扰最大；当链路i使用的信道为1，链路j使用的信道为4时，信道分离度为0.4；当链路i使用的信道为2，链路j使用的信道为7时，信道分离度为0，即忽略干扰，此处不再一一举例，该信道分离度也并不以上表10为限制。
在链路i单位时间内需要传输的数据量为qi(数据传输占用的容量或当前传输的数据量)时，链路i的已占用容量为
Figure BDA0001751796460000161
链路i的剩余容量等于
Figure BDA0001751796460000162
该链路的传输潜力CLi等于
Figure BDA0001751796460000163
在本实施例中，确定网络(例如无线多跳网络)中各个链路中传输潜力最小的链路为链路z，进而得到该链路z的传输潜力CLz，该链路z可传输的最大数据量为(1+CLz)×Qs，其中，Qs为已知的源节点的数据传输速率，该网络能力等于该链路z在单位时间内可传输的最大数据量(1+CLz)×Qs。
通过上述实施例，考虑邻居节点之间的相互影响，根据网络中数据传输已占用容量与剩余容量的关系确定网络能力，将该网络能力作为评价网络性能的指标，从而能够更加准确的评价多跳无线网络的网络性能。
实施例4
本实施例4还提供了一种多跳无线网络部署装置，由于该装置解决问题的原理与实施例1中的方法类似，因此其具体的实施可以参照实施例1的方法的实施，重复之处不再赘述。
图10是本实施例中多跳无线网络部署装置实施方式的示意图，如图10所示，该装置1000包括：
第一处理单元1001，其用于使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；
第一确定单元1002，其用于在满足预定条件时，将该第一处理单元生成的该第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
其中，该部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及该路径上的节点配置的天线信息，可选的，该部署方案还可以包括：该路径上各个链路的信道信息，该部署方案的具体表示方式可以参考实施例1，其内容合并于此，此处不再赘述。
在本实施例中，该第一处理单元1001以及第一确定单元1002的具体实施方式可以参考实施例1步骤301-302，重复之处不再赘述。
图11是该第一处理单元1001示意图，如图11所示，该第一处理单元1001包括：
选择单元1101，其用于计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数，根据每个部署方案的至少两个目标函数，计算第i代路由节点部署方案集中的每个部署方案的适应度函数，选择满足第一预定条件的部署方案得到第一部署方案集；其中，该适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比；
交叉单元1102，其用于从该第一部署方案集中，选定第二预定数量组的部署方案，其中每组部署方案包含两个部署方案，将该每组部署方案中的两个部署方案进行交叉处理；
变异单元1103，其用于从对该第二预定数量组的部署方案进行交叉处理后的第一部署方案集中选定第三预定数量的部署方案，得到第二部署方案集，对第二部署方案集中的部署方案进行变异处理，以得到该第i+1代部署方案集。
例如，一方面，该选择单元1101将至少两个(m个)目标函数进行归一化处理；将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据该至少两个目标函数建立的m维空间坐标系中；在该坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；选择该距离中的最小距离；将该最小距离的倒数作为该适应度函数，其具体实施方式可以参考图6，此处不再赘述。
例如，一方面，该选择单元1101将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量个(m1)部署方案，和/或，选择适应度函数最大的第二预定数量个(m2)部署方案，和/或，选择目标函数中至少一个目标函数是最优值的第三预定数量个(m3)部署方案，以得到该第一部署方案集。
在本实施例中，选择单元1101，交叉单元1102，变异单元1103的具体实施方式可以参考步骤501～503，此处不再赘述。
在本实施例中，可选的，该装置还可以包括：
第二确定单元(未图示)，其用于根据以该最终的部署方案部署的网络中当前传输的数据量以及以该最终的部署方案部署的网络中传输潜力最小的链路能够传输的数据量确定该网络的能力；其中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定，其具体实施方式可以参考实施例3中步骤901，此处不再赘述。
图12是本发明实施例多跳无线网络部署装置的硬件构成示意图，如图12所示，装置1200可以包括：一个接口(图中未示出)，中央处理器(CPU)1220和存储器1210；存储器1210耦合到中央处理器1220。其中存储器1210可存储各种数目；此外还存储多跳无线网络部署的程序，并且在中央处理器1220的控制下执行该程序，并存储各种预设的值和预定条件等。
在一个实施方式中，多跳无线网络部署装置的功能可以被集成到中央处理器1220中。其中，中央处理器1220可以被配置为：使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，该部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息，i为大于等于零的整数；
在满足预定条件时，将该第一处理单元生成的该第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
例如，该中央处理器1220还可以被配置为：计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数，根据每个部署方案的至少两个目标函数，计算第i代路由节点部署方案集中的每个部署方案的适应度函数，选择满足第一预定条件的部署方案得到第一部署方案集；其中，所述适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比。
例如，该中央处理器1220还可以被配置为：将至少两个(m个)目标函数进行归一化处理；将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据该至少两个目标函数建立的m维空间坐标系中；在该坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；选择该距离中的最小距离；将该最小距离的倒数作为该适应度函数。
例如，该中央处理器1220还可以被配置为：将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量m1个部署方案，和/或，选择适应度函数最大的第二预定数量m2个部署方案，和/或，选择目标函数中至少一个目标函数是最优值的第三预定数量m3个部署方案，以得到该第一部署方案集。
例如，该中央处理器1220还可以被配置为：根据以该最终的部署方案部署的网络中当前传输的数据量以及以该最终的部署方案部署的网络中传输潜力最小的链路能够传输的数据量确定该网络的能力；其中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
在本实施例中，该中央处理器1220的具体实施方式可以参考实施例1，此处不再赘述。
在另一个实施方式中，也可以将上述多跳无线网络部署装置配置在与中央处理器1220连接的芯片(图中未示出)上，通过中央处理器1020的控制来实现多跳无线网络部署装置的功能。
值得注意的是，装置1200也并不是必须要包括图12中所示的所有部件，例如还可以包括通信模块1204，此外，该装置1200还可以包括图12中没有示出的部件，可以参考现有技术。
本实施例还提供一种节点(未图示)，该节点可以是普通节点或网关节点，其可以包括传感器、CPU、通信模块、电源等模块，此外其还可以包括图12所示的多跳无线网络部署装置，也可以将多跳无线网络部署装置的功能集成到节点的CPU中，此处不再赘述。
通过本实施例的上述装置，在进行多跳无线网络部署时，考虑信道分配，从而能够优化无线网络部署方案，提高部署方案的网络性能。
实施例5
本实施例5还提供了一种网络能力确定装置，由于该装置解决问题的原理与实施例3中的方法类似，因此其具体的实施可以参照实施例3的方法的实施，重复之处不再赘述。
图13是本实施例中网络能力确定装置实施方式的示意图，如图13所示，该装置1300包括：
第三确定单元1301，其用于根据当前传输的数据量以及网络中传输潜力最小的链路能够传输的数据量确定该网络能力；其中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
在本实施例中，该已占用容量等于数据传输占用的容量与干扰传输占用的容量和，该干扰传输占用的容量表示当前传输数据的链路的容量中被干扰链路占用的容量；该链路的传输潜力等于该链路的剩余容量与该已占用容量的比值。
在本实施例中，该第三确定单元1301的具体实施方式可以参考实施例3步骤901，此处不再赘述。
图14是本发明实施例网络能力确定装置的硬件构成示意图，如图14所示，装置1400可以包括：一个接口(图中未示出)，中央处理器(CPU)1420和存储器1410；存储器1410耦合到中央处理器1420。其中存储器1410可存储各种数目；此外还存储网络能力确定的程序，并且在中央处理器1420的控制下执行该程序，并存储各种预设的值和预定条件等。
在一个实施方式中，网络能力确定装置的功能可以被集成到中央处理器1420中。其中，中央处理器1420可以被配置为：根据当前传输的数据量以及网络中传输潜力最小的链路能够传输的数据量确定该网络能力；其中，该链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
在本实施例中，该中央处理器1420的具体实施方式可以参考实施例3，此处不再赘述。
在另一个实施方式中，也可以将上述网络能力确定装置配置在与中央处理器1420连接的芯片(图中未示出)上，通过中央处理器1420的控制来实现网络能力确定装置的功能。
值得注意的是，装置1400也并不是必须要包括图14中所示的所有部件，例如还可以包括通信模块1404，此外，该装置1400还可以包括图14中没有示出的部件，可以参考现有技术。
本实施例还提供一种节点(未图示)，该节点可以是普通节点或网关节点，其可以包括传感器、CPU、通信模块、电源等模块，此外其还可以包括图14所示的网络能力确定装置，也可以将网络能力确定装置的功能集成到节点的CPU中，此处不再赘述。
通过上述实施例，考虑邻居节点之间的相互影响，根据网络中数据传输已占用容量与剩余容量的关系确定网络能力，将该网络能力作为评价网络性能的指标，从而能够更加准确的评价多跳无线网络的网络性能。
本发明实施例还提供一种计算机可读程序，其中当在多跳无线网络部署装置中执行该程序时，该程序使得计算机在该多跳无线网络部署装置中执行如上面实施例1中的多跳无线网络部署方法。
本发明实施例还提供一种存储有计算机可读程序的存储介质，其中该计算机可读程序使得计算机在多跳无线网络部署装置中执行上面实施例1中的多跳无线网络部署方法。
本发明实施例还提供一种计算机可读程序，其中当在网络能力确定装置中执行该程序时，该程序使得计算机在该网络能力确定装置中执行如上面实施例3中的网络能力确定方法。
本发明实施例还提供一种存储有计算机可读程序的存储介质，其中该计算机可读程序使得计算机在网络能力确定装置中执行上面实施例3中的网络能力确定方法。
结合本发明实施例描述的在多跳无线网络部署、网络能力确定装置中多跳无线网络部署、网络能力确定方法可直接体现为硬件、由处理器执行的软件模块或二者组合。例如，图10-14中所示的功能框图中的一个或多个和/或功能框图的一个或多个组合，既可以对应于计算机程序流程的各个软件模块，亦可以对应于各个硬件模块。这些软件模块，可以分别对应于图3,5,6,8,9所示的各个步骤。这些硬件模块例如可利用现场可编程门阵列(FPGA)将这些软件模块固化而实现。
软件模块可以位于RAM存储器、闪存、ROM存储器、EPROM存储器、EEPROM存储器、寄存器、硬盘、移动磁盘、CD-ROM或者本领域已知的任何其它形式的存储介质。可以将一种存储介质耦接至处理器，从而使处理器能够从该存储介质读取信息，且可向该存储介质写入信息；或者该存储介质可以是处理器的组成部分。处理器和存储介质可以位于ASIC中。该软件模块可以存储在多跳无线网络部署、网络能力确定装置的存储器中，也可以存储在可插入多跳无线网络部署、网络能力确定装置的存储卡中。
针对图10-14描述的功能框图中的一个或多个和/或功能框图的一个或多个组合，可以实现为用于执行本申请所描述功能的通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑器件、分立门或晶体管逻辑器件、分立硬件组件、或者其任意适当组合。针对图3,5,6,8,9描述的功能框图中的一个或多个和/或功能框图的一个或多个组合，还可以实现为计算设备的组合，例如，DSP和微处理器的组合、多个微处理器、与DSP通信结合的一个或多个微处理器或者任何其它这种配置。
以上结合具体的实施方式对本发明进行了描述，但本领域技术人员应该清楚，这些描述都是示例性的，并不是对本发明保护范围的限制。本领域技术人员可以根据本发明的精神和原理对本发明做出各种变型和修改，这些变型和修改也在本发明的范围内。
关于包括以上多个实施例的实施方式，还公开下述的附记。
附记1、一种多跳无线网络部署装置，其中，所述装置包括：
第一处理单元，其用于使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，所述部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息，i为大于等于零的整数；
第一确定单元，其用于在满足预定条件时，将所述第一处理单元生成的所述第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
附记2、根据附记1所述的装置，其中，所述每个部署方案还包括：所述路径上各个链路的信道信息。
附记3、根据附记1所述的装置，其中，所述天线信息包括：天线的波束宽度和/或天线的方向信息。
附记4、根据附记3所述的装置，其中，所述方向信息包括上行方向信息和/或下行方向信息，所述上行方向信息和/或下行方向信息为上行方向和/或下行方向与链路连线的偏离度。
附记5、根据附记1所述的装置，其中，所述第一处理单元包括：
选择单元，其用于计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数，根据每个部署方案的至少两个目标函数，计算第i代路由节点部署方案集中的每个部署方案的适应度函数，选择满足第一预定条件的部署方案得到第一部署方案集；其中，所述适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比；
交叉单元，其用于从所述第一部署方案集中，选定第二预定数量组的部署方案，其中每组部署方案包含两个部署方案，将所述每组部署方案中的两个部署方案进行交叉处理；
变异单元，其用于从对所述第二预定数量组的部署方案进行交叉处理后的第一部署方案集中选定第三预定数量的部署方案，得到第二部署方案集，对第二部署方案集中的部署方案进行变异处理，以得到该第i+1代部署方案集。
附记6、根据附记5所述的装置，其中，所述选择单元将至少两个(m个)目标函数进行归一化处理；将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据所述至少两个目标函数建立的m维空间坐标系中；在所述坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；选择所述距离中的最小距离；将所述最小距离的倒数作为所述适应度函数。
附记7、根据附记5所述的装置，其中，所述选择单元将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量个部署方案，和/或，选择适应度函数最大的第二预定数量个部署方案，和/或，选择目标函数中至少一个目标函数是最优值的第三预定数量个部署方案，以得到所述第一部署方案集。
附记8、根据附记1所述的装置，其中，所述装置还包括：
第二确定单元，其用于根据以所述最终的部署方案部署的网络中当前传输的数据量以及以所述最终的部署方案部署的网络中传输潜力最小的链路能够传输的数据量确定所述网络的能力；其中，所述链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
附记9、一种网络能力确定装置，其中，所述装置包括：
第三确定单元，其用于根据当前传输的数据量以及网络中传输潜力最小的链路能够传输的数据量确定所述网络能力；其中，所述链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
附记10、根据附记9所述的装置，其中，所述已占用容量等于数据传输占用的容量与干扰传输占用的容量和，所述干扰传输占用的容量表示当前传输数据的链路的容量中被干扰链路占用的容量；所述链路的传输潜力等于所述链路的剩余容量与所述已占用容量的比值。
附记11、一种多跳无线网络部署方法，其中，所述方法包括：
使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，所述部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息；
在满足预定条件时，将生成的所述第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案。
附记12、根据附记11所述的方法，其中，所述每个部署方案还包括：
所述路径上各个链路的信道信息。
附记13、根据附记11所述的方法，其中，所述天线信息包括：天线的波束宽度和/或天线的方向信息。
附记14、根据附记13所述的方法，其中，所述方向信息包括上行方向信息和/或下行方向信息，所述上行方向信息和/或下行方向信息为上行方向和/或下行方向与链路连线的偏离度。
附记15、根据附记11所述的方法，其中，对第i代部署方案集中的部署方案进行处理包括：选择处理，交叉处理，变异处理，其中，所述选择处理包括：
计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数；
选择满足第一预定条件的部署方案。
附记16、根据附记15所述的方法，其中，所述选择处理还包括：
计算第i代路由节点部署方案集中的每个部署方案的适应度函数；
其中，所述适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比。
附记17、根据附记16所述的方法，其中，计算第i代路由节点部署方案集中的每个部署方案的适应度函数包括：
将至少两个(m个)目标函数进行归一化处理；
将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据所述至少两个目标函数建立的m维空间坐标系中；
在所述坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；
选择所述距离中的最小距离；
将所述最小距离的倒数作为所述适应度函数。
附记18、根据附记15或16所述的方法，其中，选择满足第一预定条件的部署方案包括：
将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量个部署方案，和/或，
选择适应度函数最大的第二预定数量个部署方案，和/或，
选择目标函数中至少一个目标函数是最优值的第三预定数量个部署方案。
附记19、根据附记11所述的方法，其中，所述方法还包括：
根据以所述最终的部署方案部署的网络中当前传输的数据量以及以所述最终的部署方案部署的网络中传输潜力最小的链路能够传输的数据量确定所述网络的能力；其中，所述链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
附记20、根据附记19所述的方法，其中，所述已占用容量等于数据传输占用的容量与干扰传输占用的容量和，所述干扰传输占用的容量表示当前传输数据的链路的容量中被干扰链路占用的容量；所述链路的传输潜力等于所述链路的剩余容量与所述已占用容量的比值。

Claims (8)

1.一种多跳无线网络部署装置，其中，所述装置包括：
第一处理单元，其用于使用遗传算法，对预先获得的第i代部署方案集中的部署方案进行处理，生成第i+1代部署方案集；其中，所述部署方案集中包括多个部署方案，每个部署方案包括至少一个源节点到至少一个目的节点之间的一条以上路径以及所述路径上的节点配置的天线信息，i为大于等于零的整数；
第一确定单元，其用于在满足预定条件时，将所述第一处理单元生成的所述第i+1代部署方案集确定为最终的部署方案集；在不满足预定条件时，使用所述遗传算法，对该第i+1代部署方案集中的部署方案进行处理，直至获得最终的部署方案；
其中，所述第一处理单元包括：
选择单元，其用于计算第i代路由节点部署方案集中的每个部署方案的至少两个目标函数，根据每个部署方案的至少两个目标函数，计算第i代路由节点部署方案集中的每个部署方案的适应度函数，选择满足第一预定条件的部署方案得到第一部署方案集；其中，所述适应度函数与每个部署方案和第i-1代部署方案集中帕累托解的最小欧式距离成反比；
交叉单元，其用于从所述第一部署方案集中，选定第二预定数量组的部署方案，其中每组部署方案包含两个部署方案，将所述每组部署方案中的两个部署方案进行交叉处理；
变异单元，其用于从对所述第二预定数量组的部署方案进行交叉处理后的第一部署方案集中选定第三预定数量的部署方案，得到第二部署方案集，对第二部署方案集中的部署方案进行变异处理，以得到该第i+1代部署方案集。
2.根据权利要求1所述的装置，其中，所述每个部署方案还包括：所述路径上各个链路的信道信息。
3.根据权利要求1所述的装置，其中，所述天线信息包括：天线的波束宽度和/或天线的方向信息。
4.根据权利要求3所述的装置，其中，所述方向信息包括上行方向信息和/或下行方向信息，所述上行方向信息和/或下行方向信息为上行方向和/或下行方向与链路连线的偏离度，所述偏离度与上行方向和/或下行方向的方向角与链路连线的偏离角度有对应关系。
5.根据权利要求1所述的装置，其中，所述选择单元将m个目标函数进行归一化处理；将每个部署方案以及第i-1代部署方案集中帕累托解映射到根据所述至少两个目标函数建立的m维空间坐标系中；在所述坐标系中计算每个部署方案与第i-1代部署方案集中每个帕累托解的欧式距离；选择所述距离中的最小距离；将所述最小距离的倒数作为所述适应度函数，m为大于或等于2的整数。
6.根据权利要求1所述的装置，其中，所述选择单元将每个部署方案的各个目标函数的最大值和最小值的差值等分为N个区间，选择各个区间内的第一预定数量个部署方案，和/或，选择适应度函数最大的第二预定数量个部署方案，和/或，选择目标函数中至少一个目标函数是最优值的第三预定数量个部署方案，以得到所述第一部署方案集。
7.根据权利要求1所述的装置，其中，所述装置还包括：
第二确定单元，其用于根据以所述最终的部署方案部署的网络中当前传输的数据量以及以所述最终的部署方案部署的网络中传输潜力最小的链路能够传输的数据量确定所述网络的能力；其中，所述链路的传输潜力根据链路的剩余容量以及已占用容量的关系确定。
8.根据权利要求7所述的装置，其中，所述已占用容量等于数据传输占用的容量与干扰传输占用的容量和，所述干扰传输占用的容量表示当前传输数据的链路的容量中被干扰链路占用的容量；所述链路的传输潜力等于所述链路的剩余容量与所述已占用容量的比值。
CN201810869586.3A 2018-08-02 2018-08-02 多跳无线网络部署方法、网络能力确定方法和装置 Expired - Fee Related CN110798841B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810869586.3A CN110798841B (zh) 2018-08-02 2018-08-02 多跳无线网络部署方法、网络能力确定方法和装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810869586.3A CN110798841B (zh) 2018-08-02 2018-08-02 多跳无线网络部署方法、网络能力确定方法和装置

Publications (2)

Publication Number Publication Date
CN110798841A CN110798841A (zh) 2020-02-14
CN110798841B true CN110798841B (zh) 2022-06-24

Family

ID=69425148

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810869586.3A Expired - Fee Related CN110798841B (zh) 2018-08-02 2018-08-02 多跳无线网络部署方法、网络能力确定方法和装置

Country Status (1)

Country Link
CN (1) CN110798841B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111988220B (zh) * 2020-08-14 2021-05-28 山东大学 基于强化学习的数据中心间多目标灾难备份方法和系统
CN111681607B (zh) * 2020-08-17 2020-11-13 武汉精立电子技术有限公司 一种基于遗传算法的Gamma调节方法及系统
CN112804758B (zh) * 2020-12-30 2022-09-06 深圳清华大学研究院 多跳网络通信资源分配方法及装置
CN116032788B (zh) * 2022-12-22 2023-08-11 南凌科技股份有限公司 Sd-wan系统一种单臂部署的方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101945398A (zh) * 2009-07-07 2011-01-12 华为技术有限公司 无线网络规划方法及装置
CN102244914A (zh) * 2011-07-21 2011-11-16 东北大学 一种适用于多跳无线网络的认知路由方法
CN104429131A (zh) * 2013-11-11 2015-03-18 华为技术有限公司 选择无线接入网络的方法和装置
CN107493578A (zh) * 2016-06-13 2017-12-19 富士通株式会社 无线网络部署方法和装置
CN107872807A (zh) * 2016-09-26 2018-04-03 富士通株式会社 路由节点位置确定方法、装置和终端设备

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2337273B1 (en) * 2009-12-15 2012-10-10 Alcatel Lucent Capacity management in mesh networks
US10142909B2 (en) * 2015-10-13 2018-11-27 The Board Of Trustees Of The University Of Alabama Artificial intelligence-augmented, ripple-diamond-chain shaped rateless routing in wireless mesh networks with multi-beam directional antennas
US10313953B2 (en) * 2015-12-30 2019-06-04 Facebook, Inc. Micro-route characterization and selection

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101945398A (zh) * 2009-07-07 2011-01-12 华为技术有限公司 无线网络规划方法及装置
CN102244914A (zh) * 2011-07-21 2011-11-16 东北大学 一种适用于多跳无线网络的认知路由方法
CN104429131A (zh) * 2013-11-11 2015-03-18 华为技术有限公司 选择无线接入网络的方法和装置
CN107493578A (zh) * 2016-06-13 2017-12-19 富士通株式会社 无线网络部署方法和装置
CN107872807A (zh) * 2016-09-26 2018-04-03 富士通株式会社 路由节点位置确定方法、装置和终端设备

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
"基于共享通道保护的容量优化设计算法";许薇等;《无线电工程》;20070605;第37卷(第06期);摘要、第0、1、2.1节 *
许薇等."基于共享通道保护的容量优化设计算法".《无线电工程》.2007,第37卷(第06期),摘要、第0、1、2.1节. *

Also Published As

Publication number Publication date
CN110798841A (zh) 2020-02-14

Similar Documents

Publication Publication Date Title
CN110798841B (zh) 多跳无线网络部署方法、网络能力确定方法和装置
CN112104558B (zh) 区块链分发网络的实现方法、系统、终端及介质
CN104185242B (zh) 一种降低干扰的无线Mesh网络信道分配与路由联合优化系统与方法
CN107493578A (zh) 无线网络部署方法和装置
CN111148116B (zh) 面向应急通信的wmn网关部署与信道分配联合优化方法
Konstantinidis et al. Energy-aware topology control for wireless sensor networks using memetic algorithms
CN105074735A (zh) 通过在多个学习机器之间共享信息来加速学习
JP6881178B2 (ja) ルーティングノード位置確定方法、装置及び端末装置
CN104883702B (zh) 一种无线传感器网络网关优化部署方法
CN107343303B (zh) 无线Mesh网络中基于对偶分解的路由优化方法
CN109039886A (zh) 网络动态路由计算方法、装置及设备
US8953497B2 (en) Modified tree-based multicast routing schema
Umashankar et al. Design of high speed reconfigurable distributed life time efficient routing algorithm in wireless sensor network
Santana et al. Bio-Inspired Multi-Objective Algorithms Applied on the Optimization of the AODV’s Routing Recovery Mechanism
Zenati et al. RRO: A regularized routing optimization algorithm for enhanced throughput and low latency with efficient complexity
CN104394569A (zh) 无线d2d网络中基于角度和干扰控制建立多播路由的方法
Zhang et al. Low-overhead routing for offchain networks with high resource utilization
CN105451293B (zh) 无线网络中的转发方法、确定转发策略的方法和设备
Schleich et al. Optimising small-world properties in VANETs: centralised and distributed overlay approaches
Singh et al. Dead State Recovery Based Power Optimization Routing Protocol for MANETs (DSPO)
Kao et al. 3-D localized position-based routing with nearly certain delivery in mobile ad hoc networks
CN106507431B (zh) 无线传感器网络路由方法
Sharma et al. Influence of crossover and mutation on the behavior of Genetic algorithms in Mobile Ad-hoc Networks
EP4449687A1 (en) Distributed machine learning
CN109756902A (zh) 多跳无线网络部署方法和装置

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20220624

CF01 Termination of patent right due to non-payment of annual fee