数学建模覆盖问题篇1
关键词：应急设施选址；双目标；多级覆盖衰减；遗传算法
中图分类号：F252文献标识码：a文章编号：1001-8409（2012）12-0127-05
Bi-objectiveemergencyFacilityLocationmodelandalgorithmConsideringmulti-levelGradualCoverage
XiaoJun-hua1，2，HoUYun-xian1
（1.Schoolofeconomicsandmanagement，ChinaagriculturalUniversity，Beijing100083；
2.BeijingVocationalCollegeLaborandSocialSecurity，Beijing100029）
abstract：inallusiontothecharacteristicsoftremendousandcontinueddemandsforemergencysuppliesduringlarge-scaleemergencyoccurring，consideringthefactorsoffairness，efficiencyandcostforfacilitylocation，aBi-objectivemulti-levelgradualcoveragelocationmodelwasproposedbasedontheideaofbackupcoverageandgradualcoverageinthispaper.ageneticalgorithmprocedurebasedonmatLaB7.0wasdevelopedtosolvethemodel.acomputationalexperimentwasadoptedtoprovetheeffectivenessofgeneticalgorithm，andperformanceofthetraditionalbinarycoverageandgradualcoveragewascompared，influenceofsensitivecoefficientofgradualcoverageanddifferentcoveringradiustotheobjectiveofmodelwereanalyzed.Resultshowsthatthemodelcanprovideaneffectiveapproachforthedecisionmakerstomaketheemergencyfacilitylocationdecision.Finally，conclusionsandsuggestionsforthefutureresearchweregiven.
Keywords：emergencyfacilitylocation；bi-objective；multi-levelgradualcoverage；geneticalgorithm
引言
设施选址是选址问题的一个重要研究领域，主要采用运筹学、拓扑学等研究方法，涉及数学建模与算法设计，强调定量，或努力做到定量与定性分析的有机结合[1，2]。传统的设施选址问题可分为：p-中值问题、p-中心问题和覆盖问题[3～5]，其中，覆盖问题是设施选址问题中应用最广的模型，尤其适用于应急设施的选址。Schilling，D.a等[6]对1991年以前的覆盖问题进行了综述，Farahani，R.Z等[7]对1992～2011年的覆盖问题进行了综述。
传统覆盖问题有一个基本假设，即若需求点与设施点之间的距离小于某一距离（时间）则被认为是完全覆盖，反之则认为不会被覆盖，这种假设可以称之为0-1覆盖。学者们认识到这一假设在很多情况下是不合理的，并提出了一些改进思路：Berman，o.等[8]研究了“覆盖逐渐”的最大覆盖选址问题，马云峰[9]提出了基于时间满意度的最大覆盖选址问题，陆相林[10]提出了覆盖半径内需求满意存在差异的最大覆盖选址问题。
覆盖问题的另一个基本假设是需求点只能由一个设施点提供服务。这种假设没有考虑到设施拥塞或失效的情况。为此，Daskin，m.S.等[11]提出了多重覆盖的集覆盖模型；Hogan，K.等[12]提出考虑备用覆盖的最大覆盖模型；narasimhan，S.等[13]提出了一个考虑容量限制应急设施多水平覆盖选址模型，并用拉格朗日松弛算法进行了求解。
传统的设施选址模型多为单目标决策，而重大突发事件下，应急设施选址应综合考虑多方面的因素，需要使用多目标方法解决选址决策问题。文献[14，15]等考虑应急设施选址的公平性、效率性及成本等因素建立了多目标设施选址模型，并提出了求解方法。
基于以上分析，本文针对在重大突发事件下，需求点对应急物资的需求量巨大以及对资源的持续需求特点，基于多级覆盖和覆盖衰减思想，考虑覆盖需求量最大和选址总成本最小等因素，提出一类应急设施双目标多级覆盖衰减选址模型（Bi-objectivemulti-LevelGradualCoveringLocationproblem，BomLGCLp），并利用遗传算法对模型进行求解，比较了传统0-1覆盖与多级覆盖选址模型的优劣，并对几种覆盖衰减函数应用效果进行了对比分析；最后得出结论和研究展望。
1BomLGCLp模型建立
1.1问题描述
选址问题涉及两类站点，一类为需求站点，统称为需求点；另一类为服务站点，即应急物资储备库，统称为设施点。设施点为需求点提供服务，以距离表示设施点与需求点之间的联系紧密程度。mL-GmCLp模型假设如下：
假设1：设施点和需求点均为离散的；
假设2：任意设施点和需求点的距离为欧氏距离；
假设3：设施点可以建立在需求点上，也可以独立于需求点之外，单独建立；
假设4：设施点可以为多个需求点提供服务，且设施点服务能力无限制；
假设5：待建设施点的数量有限，为p个；
假设6：需求点有k级需求覆盖水平，且在其每一个需求覆盖水平上最多由一个设施点为其提供服务如图1所示；
假设7：设施点的覆盖对到需求点距离的增加是逐渐衰减的。
1.2覆盖衰减函数
传统最大覆盖选址模型中的覆盖是0-1型的。但是，在现实生活中，比如地震救援中，理论上区域内所有的应急设施都可以为受灾点提供救援服务，当设施点与受灾点距离小于或等于距离D时，则覆盖满意度为1，否则，覆盖满意度随距离的增加而衰减，借鉴王文峰[16]提出的方法构建覆盖衰减函数：
fkidij=1dij≤Dkα1-dij-Dkmaxdij-Dkβdij>Dk（1）
式（1）中，α和β为设施点对需求点提供服务的敏感系数，其中α∈[0，1]，β∈（0，+∞）；
max（dij）为任意设施点到需求点的最大距离；Dk为第k级覆盖水平的最大距离。
1.3模型构建
设i表示应急需求点的集合，i∈i；J表示备选设施点的集合，j∈J；从集合J中选择p个设施为每一个需求点提供K级覆盖。定义如下决策变量：
xkij=1，如果设施点j为需求点i提供k级覆盖；0，否则；
yj=1，如果设施点j被选中；0，否则；
模型参数定义：
p为选择的设施点的数量；K为需求点的需求覆盖水平；mi为需求点i的需求量；wk为第k级覆盖水平的权重，且权重之和为1；Dk为第k级覆盖水平的最大距离；dij为需求点i到设施点j的距离；Cj为设施点j的建设成本；υ为物资单位距离的运输成本。
双目标多级覆盖选址模型（BomLGCLp）：
问题p：
Z1=max∑i∈i∑j∈J∑k∈Kwkfkidijmixkij（2）
Z2=min∑j∈Jcjyj+υ∑i∈i∑j∈J∑k∈Kwkfkidijmidijxkij（3）
Subjectto：
∑j∈Jyj=p（4）
∑j∈Jxkij=1i∈i，k∈K（5）
xkij≤yji∈i，j∈J（6）
xkij，yj∈0，1i∈i，j∈J，k∈K（7）
目标函数（2）是使需求点在各需求覆盖水平上被覆盖的总需求量最大；式（3）使总的成本最小化；式（4）规定需要建立的设施点的数量；式（5）表示需求点在各需求覆盖水平上最多只能由1个设施点提供服务；式（6）则表示只有当设施点被选定时，才能为需求点提供服务；式（7）表示yj和xkij均为二元整数决策变量。
2模型求解分析及算法设计
2.1模型求解分析
多目标规划可同时处理两个或两个以上具有冲突关系的目标，因此多目标规划所求得的解是一个pareto最优向量[17]。常见的多目标规划的解法主要有：约束法、分层序列法、功效系数法、评价函数法、乘除法、层次分析法等[18]。分层序列法的思想是把目标按其重要性给出一个序列，分为最重要目标、次重要目标等。设给出的重要性序列为f1（x），f2（x），…，fm（x）。首先对第一个目标求最优，并找出所有最优解的集合记为R0，然后在R0内求第二个目标的最优解，记为R1，如此一直求出第m个目标的最优解，即得到多目标规划的满意解[19]。本文应用分层序列法对模型进行如下分解：
问题p1：
Z1=max∑i∈i∑j∈J∑k∈Kakifkjdijxkij（8）
Subjectto：（4）-（7）
问题p2：
Z3=min∑j∈Jcjyj+∑i∈i∑j∈R∑k∈Kakicijdijxkij（9）
Subjectto：（4）-（7）
其中：R为p1中所有pareto解的集合。
2.2遗传算法设计
最大覆盖选址模型已经被证明为np-Hard问题[20]，而本文所建多级覆盖衰减选址模型是最大覆盖模型的扩展，所以也是np-Hard问题。由于该类问题计算复杂度较大，难以利用精确算法进行求解，只能借助于启发式或近似算法来求得其近似解。本文运用遗传算法对模型进行求解。作为一种有效的全局搜索方法，遗传算法的应用领域已渗透到多个学科[21]。越来越多的研究者将遗传算法应用在设施选址领域，研究文献包括求解集覆盖问题、p-中值问题和最大覆盖问题等[22]。遗传算法主要技术如下：
（1）编码方案
对所有的备选设施点按1至n进行赋值，每个代码表示一个基因。每个染色体代表模型的一个可行解，染色体的每一个基因代表选择的备选设施点，设定染色体长度为p。
（2）初始种群的产生
为了确保每个设施点都有机会被选择，初始种群中的每个染色体通过随机的方法生成。借鉴文献[22]的方法，将种群的规模定义为n=max{100，1.2[J/p]}，其中“[]”表示向下取整数。
（3）适应值赋值
种群中每个染色体的适应度评估由目标函数式（8）和式（9）来计算。适应度计算过程如下：
步骤1：选择第一个需求点，计算其到染色体中每一个基因的距离，对距离进行升序排序，选择前k个距离dk；
步骤2：判断距离dk与各覆盖等级最大距离Dk的关系，并由覆盖衰减函数判断每一个基因所代表的设施点为需求点提供的最大物资量，求出需求点得到的总物资量，并计算物资运输的最小成本；
步骤3：重复步骤1～2，遍历全部需求点，得到全部需求点获得的总物资量和物资运输的总成本。
（4）选择、交叉和变异操作
父代的选择采用从群体中随机选择的方式。交叉采用非标准的交叉方式产生子个体，首先将两个父代个体合并为一个长度为2p的个体，并去掉个体中的重复点，然后采用贪婪取走算法去掉个体中对目标值贡献最小的基因，直到剩余p个基因即为子个体。
在变异过程中，随机选择一个染色体，从选择的染色体中随机选择一个基因然后替换为一个与原染色体中基因不重复的新的基因。将变异率设为0.1。
（5）终止条件
在每次迭代中，记下适应值最大的染色体，直到已经达到了算法规定的最大迭代次数时算法终止。当算法终止时，最好的染色体即是该选址问题的最优解。
（6）遗传算法具体操作流程
步骤1：对数据进行实数编码，构造备选设施点与需求点之间的距离矩阵Cm×n；定义遗传算法参数（群体规模n、最大遗传代数maxgen、交叉概率pc、变异概率pm）。
步骤2：用随机的方法生成初始化种群p（0），令t=1，p（t）=p（0）。
步骤3：计算种群p（t）的适应值。
步骤4：用随机选择策略选择两个父个体p1和p2，进行交叉、变异、重插入等操作得到子种群Q（t）。
步骤5：将p（t）和Q（t）合并，得到新的种群R（t）。
步骤6：对新种群R（t）进行优劣排序，得到p（t+1）。
步骤7：t=t+1，判断是否满足结束条件，如果否，转步骤3；否则结束，输出结果。
3算例分析
假设某地区有30个需求点，当地政府计划从15个备选地点选择建设一定数量的应急设施点以应对突发事件，目标是以最小的总成本来最大化满足突发事件发生时的应急需求。需求点和备选设施点的位置在一个[0，100]的平面上均匀分布，需求点和备选设施点的坐标如表1和表2所示；假设各需求点应急物资为单一种类，且需求量在区间[3，5]间随机产生，单位为万件；设施点的固定建设费用均为100万元；单位产品的运输费用Cij=0.1×dij，dij为需求点i与设施点j间的距离。各覆盖等级的覆盖半径由式Dk=Dmin+mk（Dmax-Dmin）确定，其中mk为各等级覆盖半径的乘数，Dmin和Dmax为需求点到备选设施点的最小和最大距离；为了比较不同覆盖距离下，设施点覆盖满意度和服务成本之间的关系，本文分别设mk为（0.05、0.1、0.15）、（0.1、0.2、0.3）和（0.2、0.4、0.6）；假设多级覆盖为3级覆盖，需求点对各覆盖等级的需求量分别为需求点总需求量的60%、30%和10%。应用matlab7.0设计遗传算法程序，并在DeLLn4040笔记本电脑上进行计算。
3.1传统0-1多级覆盖模型和多级覆盖衰减模型的比较
由式（1），当α=0时，覆盖衰减函数转化为0-1结构，此时问题p为传统0-1多级覆盖问题。选择5个设施点，对传统0-1多级覆盖模型和多级覆盖衰减模型的性能进行比较，其中覆盖半径乘数mk为（0.1，0.2，0.3），覆盖衰减函数的敏感系数当α=0，β=2。表1比较了两种模型的性能，图2为两种覆盖模型的选址结果。
3.2覆盖衰减函数的敏感度分析
多级覆盖衰减选址模型中的覆盖衰减函数敏感系数α，β的不同取值将对模型的覆盖满意度产生不同的影响，此处假设α=1，β分别取0.5、1、2，覆盖半径乘数mk为（0.1，0.2，0.3），分别比较当选择设施点数分别为4、5、6、7、8、9时的覆盖满意度。如图3所示，当α=1，β=0.5时，多级覆盖衰减选址模型在选择不同个数的设施点时均取得了最大的覆盖满意度。因此在接下来的选址过程中，覆盖衰减函数的敏感系数可选择α=1，β=0.5。
3.3不同覆盖半径下的设施成本、覆盖满意度的敏感度分析
多级覆盖衰减选址模型在不同的覆盖半径下，在选择不同数目的设施时，设施选址的成本、覆盖满意度均有所不同。此处假设模型覆盖半径乘数mk分别取（0.05，0.1，0.15）、（0.1，0.2，0.3）和（0.2，0.4，0.6），比较当选择设施数分别为4、5、6、7、8、9时，分析不同覆盖半径下多级覆盖衰减选址模型的性能，如表2所示。
由表2，在不同覆盖半径下，模型覆盖满意度均随选择设施点数量的增加而增加；在选择相同数目的设施点的情况下，覆盖满意度随着覆盖半径的增加而增加，当覆盖半径乘数mk取（0.2，0.4，0.6），选择设施点数目为8时，覆盖满意度达到100%；在选择设施点个数确定时，运输成本和总成本均随覆盖半径的增加而增加；当模型覆盖半径确定时，运输成本随选择设施点个数的增加而降低，总成本随设施点个数的增加而增加。决策者在进行选址决策时，可根据本地的实际情况，综合考虑覆盖满意度和选址成本进行决策。
3.4覆盖满意度为100%时的选址决策
如表2所示，当要求设施覆盖满意度达100%时，决策者可选择覆盖半径乘数为（0.2，0.4，0.6），选择建立8个设施点，选址方案为（2，3，5，7，8，10，13，14），每个设施点在不同覆盖等级服务的需求点如表3所示。
4结论及研究展望
本文主要研究了多级覆盖衰减的应急设施选址问题，提出了一个双目标的整数规划模型。然后运用遗传算法对模型进行了求解并进行了算例分析。算例结果显示，多级覆盖衰减选址模型较之传统0-1多级覆盖选址模型有更高的覆盖满意度。当敏感系数α和β分别取1和0.5时，模型可以取得更高的覆盖满意度。模型覆盖满意度随设施点个数的增加而增加；在设施点个数确定时，覆盖满意度随着覆盖半径的增加而增加；总成本随设施点个数和覆盖半径的增加而增加；在规定覆盖半径下，运输成本随设施点个数的增加递减，总成本随设施点个数的增加递增。最后本文还给出了当要求设施完全覆盖需求点的情况下，设施选址方案以及各设施在不同覆盖等级服务的需求点集合。
本文提出运用分层序列法对双目标模型进行求解。仅当前面的重要目标有多个pareto解时，后面的次要目标才有意义，当重要目标仅有一个最优解时，则次要目标就失去了求解的意义。因此，在实用中，可为重要目标设定一定的宽容量，以保证双目标规划模型的有效性。
参考文献：
[1]杨丰梅，华国伟，邓猛，黎建强.选址问题研究的若干进展[J].运筹与管理，2005，14（6）：1-7.
[2]王非，徐渝，李毅学.离散设施选址问题研究综述[J].运筹与管理，2006，15（5）：64-69.
[3]RothputerSolutionstominimumCoverproblems[J].operationResearch，1969（17）：455-465.
[4]toregasC，SwaimR，ReVelleCandBergmanL.theLocationofemergencyServiceFacilities[J].operationResearch，1971（19）：1363-1373.
[5]ChurchRandReVelleC.maximalCoveringLocationproblem[J].papersoftheRegionalScienceassociation，1974（32）：101-118.
[6]SchillingDa，JayaramanVandBarkhiR.aReviewofCoveringprobleminFacilityLocation[J].LocationScience，1993，1（1）：25-55.
[7]FarahaniRZ.CoveringproblemsinFacilityLocation：aReview[J].Computersandindustrialengineering.2012，62（1）：368-407.
[8]Bermano，DreznerbZandKrassD.GeneralizedCoverage：newDevelopmentsinCoveringLocationmodels[J].ComputersandoperationsResearch，2010，（37）：1675-1687.
[9]马云峰，杨超，张敏等.基于时间满意的最大覆盖选址问题[J].中国管理科学，2006，14（2）：45-51.
[10]陆相林，侯云先，林文，申强.基于选址理论的小城镇应急物资储备库优化配置—以北京房山区为例[J].地理研究，2011，30（6）：1000-1008.
[11]DaskinmSandSterneH.aHierarchicalobjectiveSetCoveringmodelforemergencymedicalServiceVehicleDeployment[J].transportationScience，1981（15）：137-152.
[12]HoganKandReVelleC.ConceptsandapplicationsofBackupCoverage[J].managementScience，1986（32）：1434–1444.
[13]narasimhanS，pirkulHandSchillingDa.CapacitatedemergencyFacilitySitingwithmultipleLevelsofBackup[J].annalsofoperationsResearch，1992，40（1）：323-337.
[14]陈志宗，尤建新.重大突发事件应急救援设施选址的多目标决策模型[J].管理科学，2006，19（40）：10-14.
[15]李国旗，张锦，刘思婧.城市应急物流设施选址的多目标规划模型[J].计算机工程与应用，2011，47（19）：238-241.
[16]王文峰，刘新亮，郭波.综合多准则决策的保障设施选址-分派方法[J].系统工程理论与实践，2008，5（5）：148-155.
[17]韩庆兰.物流设施规划的多目标优化模型[J].控制与决策，2006，21（8）：957-960.
[18]万凤娇.基于多目标规划的危险废弃物物流选址一选线模型研究[D].武汉：武汉理工大学，2010.
[19]运筹学[m].第3版.北京：清华大学出版社，2007.
[20]KarivoandHakimiS.analgorithmapproachtonetworkLocationproblem[J].SiamJournalofappliedmathematics，1979（37）：513-560.
数学建模覆盖问题篇2
无线网络仿真软件的操作及注意事项
1前期准备
为保证软件正常运行，操作者需具备无线专业领域基础知识，需准备软件资料，软件运行基于的操作系统和数据库的信息及使用手册，软件注册资料等相关信息。然后安装仿真软件及数据库等相关组件并联合调试。
2软件的操作使用
各软件研发思路、算法实现、操作平台、关联数据库几乎都不相同，其操作界面，功能菜单及使用方法等也各有差异，但归纳来说基本可分为四个步骤：输入数据、链路预算、模拟仿真和输出结果。
（1）输入数据是对需要模拟仿真的地区无线通信环境和无线规划优化信息等原始数据的输入。数据输入是执行模拟仿真至关重要的第一步。无线信号受地形地貌影响较大，地图信息的精准度、地形地貌数字信息与现状的差异度都将直接影响模拟仿真输出结果。因此准确输入上述地形地貌信息，天线参数信息是后续模拟仿真越接近真实情况的关键。
（2）链路预算或传播损耗计算是覆盖预测的核心。选择传播模型是链路预算的重要环节之一。绝大多数软件都提供多种常用的传播模型（okuruma-Hata，Cost-Hata，Spm等），有些软件还提供自己的模型以备选择。最好能够使用Cw测试数据来校正所选传播模型，如若没有Cw测试数据那么也可选择经典传播模型作为预测基础。为了提高预测结果的可信度和精度，需为预测范围内的多种地形类型分别设置对应的传播模型参数。一般来说，仿真软件对模型的修正都提供了参数修改功能。鉴于终端位置分布、终端软切换状态等不确定性，必须先期建立一个模型，并做一些简化性的合理假设，然后才能获得一个统计性的结果。结合已设定的基站设备参数，可进行链路预算、传播损耗计算，最终获得研究区域各站点的覆盖性能报告。
（3）模拟仿真的运行必须基于一个预测模拟的业务环境。一般在覆盖预测完成后、模拟仿真进行前，需进行如覆盖图精度与接收机高度设置、软件计算区域设置、业务类型设置、用户密度设置、移动性类型设置、业务行为设置、接收终端设置等业务相关参数的设置。
（4）3G无线网仿真软件的主要输出仿真结果有：最优小区覆盖图、信号场强覆盖图、重叠区域覆盖图、下行链路噪声图、导频接收分析图、切换状态图、导频污染图等。
3需要注意的问题
3G无线网络建设过程中，需要密切关注，也最需要解决的几个问题是覆盖问题、容量问题和干扰问题。在建网的初始阶段到工程优化阶段，所做工作主要是想方设法解决这几个问题。在网络不断加大建设的情况下，运营商对网络规划、快速建网、网络优化进行了精细化的管理，在管理与建设方面相应也有了更高的要求。怎样可以更有效地解决这些问题已经成为提高网络建设质量的重中之重。
无线网络仿真软件在无线网络优化中的运用
在CDma20001X/eV-Do建网初期，站点数量有限，网络优化的重心是解决弱覆盖等问题。随着3G系统建设的加快，移动用户数增加，话务密度和覆盖要求上升，用户对业务种类的要求更趋多样化，现在CDma20001X/eV-Do网络所要面对的问题已经从弱覆盖转变为干扰问题，而由于pn复用造成的影响也日益受到重视。无线网络优化仿真软件在科学建模的基础上，综合考虑各扇区覆盖范围、邻区关系、pn复用距离等因素，能够实现pn码的自动优化，从而实现对CDma20001X/eV-Do网络的优化。
数学建模覆盖问题篇3
关键词：材料计算；微观模拟；3D显示；算法
中图分类号：tp274文献标识码：a文章编号：1009-3044(2011)12-2932-04
材料制造业是国民经济的物质基础、国家安全的重要保障和国家竞争力的主要体现。近年来，随着材料学的深入研究开展，新材料微观结构三维显示研究逐渐成为发展新材料需要解决的问题。
传统新材料的开发采用的是代表性体积元法，通过假设出的一定体积元，来代表具有规则的、周期性分布的微观结构[1]。这种方法一般用于非均质材料，对于多晶体材料则不能表示具有不同尺寸、形状等参数的晶粒组织。以上方法还要配合复杂的材料计算、反复的试验测试，这无疑将提高创造新材料的成本。随着计算机技术在材料学中的应用日益广泛，研究新材料已不再盲目地依靠实验室中的重复试验，而是运用科学的算法在日益强大的计算机中模拟材料的微观结构仿真模型、材料的抗拉伸及抗腐蚀等各种性能。这种通过电脑对材料进行显微分析的方法，使研究人员能够更好、更直观、快速的理解材料的深层原理，从而有效缩短研究周期，降低开发成本。
材料科学主要研究材料的晶粒组织、亚组织等微观的结构和分布,然后才能对结构和分子的分布进行分析和对比，进而开展材料科学方面的其他研究。建立材料的显微模型，能够有效地反映材料微观组织的晶体分布、结晶数量、聚合程度等，这些数据与材料各外在属性是密切相关的。所以，材料学中结构的可视化显示在材料学中占有很重要的作用。而3D可视化显示在材料计算中广泛需要，是三维空间图像表现即原子排列问题是其中一个主要问题[2]。本文即主要探讨球冠逐步覆盖算法及利用openGL实现的方法[3-9]，研究球体表面密布算法问题的求解，实现在一个球体表面上布满小球且小球均匀分布不能叠加地进行显示，以及材料模拟原子排列三维微观组织结构的显示，拓展材料学研究的领域。
1三维微观组织结构显示的覆盖算法分析
通常人们可以考虑利用空间几何思想求解原子间排列的密布问题，假设一个球体集，半径为R，在其表面密布着一层小球，小球半径为r（小球不得重叠且可以相切）。因此，问题就在于，要找出若干个半径为r的球体，能够覆盖半径为R的球体的表面。起初我们是将大球体按南北极经纬线的方法划分，并在其极点及各经纬线交点处放置小球（大球半径直接关系到小球密布的数量），但实际上是不可行的。原因在于处在极点附近的小球无论半径设定多小都会出现重叠问题，此法不能使用。
球内接正多边形的方法，试想球体内接一个正多边形，在正多边形与球面相交的每个交点上放置一个小球，方法可行。但带来的问题是交点灵活，小球的半径与正多边形的边长密切相关，而且还要考虑正几面体可以直观的显现小球密布大球最复杂的是内接多面体边数变小球半径随着变。该方案也不适合。
最后，我们收集各种资料整理思路决定采用宏观看问题的方法，既不锁定球的极点也不注重球面交点，从类似足球的表面图形着手，即球的内接正12面体，以每个面的中心为小球球心所在的轴线，逐步思考推算坐标，来解决球体的密布问题。
因为球内接正12面多边形酷似菠萝，故称这种算法传统被称为菠萝形算法。
菠萝型算法：在密布问题中考虑大球的下列内接多面体。它有两个面是正n边形a1a2...an和B1B2...Bn，其外接圆的半径都是R，并且这两个面彼此互相平行，另外的2n个面均是全等的五边形，外接圆的半径也是R（图1）。当n=5时，这个多面体就是球的内接正12面体。因为这个多面体形如菠萝，故称这种算法为菠萝形算法，这种算法共需2n+2个小球。
采用球面极坐标，并设R=1，设o1o2是垂直于面a1，a2，...，an的直径，它与该面的交点o3,即为该正n边形的中心。取经过o1o2与五边形a1a2C2D1C1的顶点D1的半平面为半平面θ=0，而o4是这个五边形的外接圆圆心。那么,五边形a1a2C2D1C1关于平面θ=0是对称的，且a1、C1在同一条径线上，因此可设这些点的坐标为（设R=sinφ0）：o3（cosφ0,0,0）,a1(1,φ0,π/n)，o4（cosφ0,φ1,0）,C1(1,φ2,π/n),D1(1,π－φ2，0)。
由o4a1=o4C1=o4D1=sinφ0，得到：
tanφ0sinφ1cosπ/n+cosφ1=1，sinφ1sinφ2cosπ/n+cosφ1cosφ2=cosφ0.
这些方程的解列于表1。
其中，各个小球的中心为（cosφ0，0，0）、(cosφ0,π,0)、（cosφ0,φ1,2mπ/n）(m=0,1,…,n-1),（cosφ0，π－φ1，(2m+1)π/n）（m=0,1,…,n-1）。
菠萝型算法解决球体密布问题效果较好，但存在计算效率与覆盖到最后有空隙无法继续覆盖等问题。因此，参考一些资料对菠萝型算法继续改进。
2材料模拟的三维显示的球面密布方法――球冠逐步覆盖算法
在材料计算模拟的三维制图过程中，球体表面密布问题是基本的问题，但是一般方法建立数学模型相对复杂繁琐，尤其涉及到算法更是无从下手。菠萝形算法及其衍生方法――球冠逐步覆盖法是一个比较直观的解决和理解球面密布问题的方法。
该算法是通过分析球冠，将球冠分层，并把每层的纬圆分成n等分，做出该纬圆的内接正n边形a1a2...an（取n的大小使得边长a1a2≈r1=sinφ0，r1为球体表面覆盖的小球半径；φ0为输入参数）。
所谓球冠逐步覆盖法：就是给定大球半径R=1，小球半径r=sinφ0,φ0为输入参数（图2）。
k=0,第0层覆盖仅含一个小球，球心的坐标为（cosφ0,0,0）,=φ0.
球冠覆盖模块（参数，已覆盖区域φ≤）：
把纬圆φ=分成n等分，作出该纬圆的内接正n边形a1a2…an（取n的大小使得边长a1a2≈r1=sinφ0），ai坐标
ai（1，，（2i－1)π/n）（i=0,1,…,n－1）.
令：
当φ1＞π/2时，取φ1=π/2.
k=k+1,第k层覆盖包含n个小球，球心o1，o2，…，on坐标为
r(oi)=cosφ0,φ0（oi）=φ1
θ（oi）=2iπ/n（i=0,1,…,n－1）.
当φ1=π/2时，转输出模块Ⅰ，否则求出各小球的覆盖范围（如a1,a2,C2,D1,C1）：C1，C2坐标r（C1）=r（C2）=1，φ（C1）=φ（C2）=φ2，θ（C1）=-π/n,θ（C2）=π/n.
其中，
数学建模覆盖问题篇4
【关键词】无线宽带；覆盖；大学校园；方案
伴随着网络信息化在大学校园的普及，校园网络已成为高校师生获取信息资源的主要途径，是其校园生活的重要组成部分。无线网络以其自由移动、灵活高效等特性深受高校师生们的青睐，现已成为现代化大学校园网建设的发展趋势。而笔记本电脑的普及也使网络访问能够突破有线网络的局限，为师生随时随地访问校园网络提供了基础性条件。同时，校园网络也是一个蕴藏有丰富知识的宝藏，如此宝贵的资源理应实现充分的共享。高校师生需要尽可能更为方便、快捷、移动式使用网络，他们不仅要求无线宽带覆盖整个大学校园，而且希望能够进行校际互联。况且，一些具有较大规模的高校拥有着多个分校区，校本部与各个分校区的互联互通也已成为校园网络建设的重要一环。这对校园网的建设者、管理者来说，是亟须思考解决的现实问题。
一、无线宽带覆盖是大学校园网络建设的必然要求
大学校园无线网络建设主要是为了帮助高校教师及管理人员提升工作效率，在满足高校教学、管理、科研、服务工作中的移动应用需求的同时，提高学生学习的质量和水平。因此，大学校园网络建设必然要求上网方便快捷、机动灵活。相比传统的有线网络，无线局域网的机动性、方便性、扩充性等优势是显而易见的。
机动性是驱使无线通讯发展的根本动力，最近几年来，携带方便、轻薄短小的笔记本电脑的普及，致使笨重的桌上型计算机已经渐渐被取代，这就很能说明问题。然而，仅仅依靠笔记本电脑和个人数字助理pDa都还是远远不够的，要保持无时无刻的网络连结和信息的高效传递，离开无线通讯是不行的。为计算机带来很大机动性的，是无线局域网络wLan，它使高校师生传统的工作、学习与生活状态彻底改观。
无线局域网wLan的优长，还包括其便利性与弹性。它无需大量布线，较传统网络架设方便，并且对网管人员而言，极少需要管路来架设网络线缆，这样不仅大幅缩减了建构网络的时段，以后网络拓扑需要更动的时候，也不必要进行大规模的重新拉线。由于wLan用无线电波连接取代了铜线或光纤电缆，这在调整上方便了许多，无需为了网络线插孔的移动而大伤脑筋，信息之随手可得简直如同空气一般，很适合网管人员的弹性规划运用，尤其对商业上的应用很具有吸引力。
良好的扩充性是无线局域网wLan的另一个优点。铺设传统的有线网络，网管一般会为了预防此后额外需要的架设，往往在初次架设时造成不必要的浪费。因其可大可小，wLan的扩充与升级都比传统有线网络方便得多。只需要增加无线接入点ap，即可拓展整个网络的容量与涵盖范围，因此，对网管人员而言，安装wLan也是明智的选择。
二、无线宽带网络覆盖的基本原理
最简单的wLan，即所谓对等（peer-to-peer）网络，只需两个置于有效距离内、装有无线适配卡（wirelessadaptercard）的pC，无需经过特殊组合也不必有专人管理，更不需要中央服务器（centralserver），两个移动式pC之间是可以相互对通的。
无线网络访问点ap，可将aD-Hoc网络移动室pC之间的有效距离增大到原来的2倍。连接在有线网络上的访问点，可使移动式pC之间经过服务器而实现网络的互连互通。而每个访问点都能容纳许多pC，其容量可根据数据传输的实际要求达至15到63个pC。由于pC和无线网络交换机之间的有效距离在户外约300米、在室内约150米，大学校园内通常需要多个访问点，需事先考察选定网桥位置，以使wLan无线宽带能够覆盖整个校园，使所有师生用户都能在一群访问点的覆盖范围内漫游（roam）并确保通讯不致中断。可用ep增大网络的转接范围，以解决覆盖问题。ep的功能与访问点类似，但它并不是接在有线网络上。ep把信号从一个ap传递到另一个ap或ep，由此延伸无线网络的覆盖范围。将ep串在一起，讯号即可从一个ap传递至远方。
可通过安装定向天线来实现楼宇之间无线网络范围的扩展，要互相对准天线的方向，使两个或多个相距较远的建筑物能够接通无线网络。作为共享介质的wLan，并非为每个接入设备提供专线速度，而是分割可用的吞吐量为若干份。这就要求无线网络的吞吐量规划，必须在计算接入点数目时多预留一些空间。来自网络内部其它接入点甚或是网络外部的干扰是时常遇到的，允许用户漫游（20%到30%为最佳）靠的是一定量的良性蜂窝覆盖重迭。
影响wLan覆盖范围的因素，既有射频带及吞吐量变化造成的波传播特征，又有自由空间路径损耗和衰减的限制。可将自由空间路径损耗视为开放或户外环境问题，其实质在于无线电信号因波前扩展而引起的扩散，以至于接收天线难以接收到信号。在wLan的室内安装中，比较常见的衰减，其主要成因是振幅下降或射频信号在穿过墙、门或其它障碍物时减弱。wLan在密集建筑物周围性能较差，原因就在于此。
三、无线宽带覆盖大学校园具体方案
根据大学校园网络的实际情况，有几种具体的无线覆盖解决方案是切实可行的，简述如下以供选择。
方案一：实施多点覆盖，并且在ap覆盖点使用“BwB510a+全向天线”，每个ap可接入并发用户约为30个，可采用就近接入方式使之与internet网络连接。单ap无阻挡是此方案的基本要求，约为1.5公里的覆盖半径。和wirelessmeSHnet模式相类似，ap覆盖点的形成要靠一个几百或千兆光纤的高宽带接入点。2.4GHz模块外接2.4GHz全向天线用于周边360°，以使BwB510a的双模块无线覆盖的优势得到发挥，而5.8GHz模块利用自带扇区天线回传宽带信号给附近辅覆盖点5.8GHz的定向天线，并通过2.4GHz的全向天线实行周边范围的覆盖。
方案二：对校园内的楼宇通一规划，采用RRU、光纤直放站等方式进行手机信号的覆盖。同时在分布系统中合路wLan信号。本工程采用7个RRU，21个光纤远端机进行覆盖，同时安装了134个ap，实现校园内手机信号和宽带信号的全覆盖。搭建此无线网络，可使用美国Ubiquiti公司推出的nanoStation系列产品。例如进行室外覆盖，可选用nanoStation2产品。首先，按5000人计算，同时上网的人数概率约25%，即1250人左右，设若每人分配1m带宽，总带宽共需1250m，按nanoStation2净吞吐量21m来计算的话则需要60台设备，为免除信号盲区和便于日后扩容，可以增加nanoStation2设备2至3台，酌情机动安置。工作在2.4GHz的nanoStation2，因其支持802.11b/g协议，故能软件配置成路由器或网桥。于nanoStation2内布置水平覆盖60度角的天线，且要有Sma天线接口，就能外接全向天线、栅格天线等各种天线，现场应用更为方便。
方案三：建立一个宽带接入点，接入BwB510a设备时依凭100mbps光纤宽带，并以中间加功分器使两个90°2.4Ghz扇区天线之覆盖半径连接起来，实行3公里左右无死角、无阻挡的覆盖。用户端采用改装后的Cpe设备，凭借自带天线接收无线上网信号并且借助内置网卡与无线网络连接，再通过网线改装的USB延长线连接到计算机，从而实现无线上网功能。
参考文献：
数学建模覆盖问题篇5
【关键词】Femtocell解决方案 家用基站 家庭覆盖
随着移动宽带化、基站小型化以及移动应用场景逐步向室内转移的趋势愈加明显，Femtocell自2009年以来已经成为行业热点，据FemtoForum(Femto领域最有影响力的国际组织，拥有120多家成员，包括运营商、系统设备商、终端厂商、芯片厂商等产业链上下游成员)透露，截至目前，已有Vodafone、orange、Verizonwireless、Sprint、DoComo、中国联通、StarHub等十多家全球知名运营商推出了wCDma和CDma制式的家用基站商用或试商用服务，该领域的主要供应商则包括华为、诺基亚西门子、阿尔卡特朗讯、三星、neC、airvana、picoChip等业内知名厂商。
1 Femtoceil商业模式将成决定未来走势的关键因素
从推出伊始，Femtocell就面临着模式问题：Femtocel如何进入客户的家中或企业所在场所?是客户购买还是运营商免费提供?如何和固定宽带相结合?提供哪些差异化的增值业务?采用何种资费从而赢得客户的选择?
在业界看来，Femtoceii是实现3G室内覆盖以及固定移动融合业务的高效解决方案。用户或中小企业在家里或办公场所安装Femtocellap(accesspoint)之后，各处都有优质3G信号覆盖，家庭用户或企业用户可以获得更经济、内容更丰富的融合业务。用户在室内通过固定宽带接入移动网络或互联网，在室外则切换到移动网络，从而降低移动资费。
从短期来看，Femtocell由于同时具备互联网接入与移动这两个特性，因此能成为业务捆绑的有效手段，能够捆绑宽带接入业务与家庭，企业成员手机业务。Femtocell有助于运营商引入新的计费和业务捆绑策略，运营商可以借助Femtocell提供新型增值服务。运营商推出针对家庭或企业的资费套餐，可通过Femtocell“捆绑”家庭成员或企业成员都使用该运营商的各种基本语音业务，以及基于位置的应用等增值业务。
长期来看，Femtocell将会与家庭网关、企业网关、企业信息机之类的设备集成，成为全新的业务融合平台，真正实现互联网、tV、固定和移动的四重播放(Quadrapleplay)。
2009年是中国3G开局之年，Femtocell正式进入中国这个全球最大的3G市场，一年多以来，中国联通与华为等供应商就Femtocell除技术可行性之外的商业模式等问题进行了深入的探讨和试点验证。从研究的结果来看，商业模式的关键在于市场价值问题；而从运营商的角度来看，市场价值就是Femtocell的投资收益(Roi)问题。从最终用户的消费行为调研分析和财务测算来看，Femtocell对于中国联通以FmC业务快速发展3G用户、提升用户的aRpU值等方面会发挥积极有效的作用；同时，如果Femtoceil的商业应用达到一定的规模，长期投资收益也令人看好。
2 中国联通多场景验证Femtoeell解决方案，实现3G网络最佳覆盖
除了商业模式这个永恒的话题之外，还有一个问题始终困扰着业内人士，Femtocel嘲译成“家用基站”这个中文词汇是否完全体现其功能?引申出来就是这样的一个问题：Femto到底将用于哪些场景，除了家庭之外是否还有中小企业办公场所?或还有其它地方?
在传统的家庭覆盖、融合业务等需求上，在华为等解决方案供应商的支持下，中国联通从2009年开始在北京等十多个省份推出了名为“3G驿站”的Femtocell商用业务，此外中国联通还在四川、湖北、辽宁等多个省份进行了中小企业等场景的Femto覆盖试点测试与验证工作。综合一年来中国联通在各地的试点情况看来，Femtocell解决方案是多种场景下解决成本、覆盖、容量问题的最佳3G网络覆盖解决方案，预计2011年将得到更大规模、更大范围的部署。
2010年初，由华为提供的高性能、体积、重量、造型更契合消费者需求的新一代Femtoce¨家用基站产品已经顺利完成工信部电信设备入网测试，中国联通各省分公司后续将根据经验进行更大规模的部署，为Femtocell大规模进入各种无线场景奠定坚实的网络基础。
(1)上海联通创新应用Femtocell解决方案，实现历史保护建筑3G覆盖
位于上海中山东一路12号的上海浦东发展银行大楼(如图1所示)是外滩万国建筑群中单体最大、建造最精良的一栋历史保护建筑。由于历史建筑的花岗岩外墙、大理石隔段对宏网络基站信号造成衰耗率较高，同时因开凿、穿孔、拉线可能对内部珍贵的彩绘墙面造成不可弥补的损伤，该楼宇的3G覆盖问题一直悬而未决。为了有效支撑3G业务发展，尽快为客户带来3G精彩体验，上海联通在与供应商――华为经过深入和沟通和验证后，积极创新，一改传统的宏站和室内覆盖建设方式，利用Femtocell家用基站解决方案试点实施了该楼宇的3G室内覆盖。
经过精密的前期勘察、设计和现场安装、调试优化，浦发银行的3G网络覆盖顺利完成。开通测试显示：用户手机信号显示满格；语音业务主被叫正常、话音清晰；可视电话业务正常、画面流畅；数据业务实现最高5mbps(下行)门mbps(上行)的单用户业务体验。综合来看，Femtoceii解决方案为用户提供了与室内覆盖相近的业务体验，浦发银行客户对此非常满意。如图2所示。
(2)FemtocelⅡ全球首度进入高校校园，天津联通获信息化金奖
在中国联通看来，Femtocell家用基站是放置在家庭、楼宇等室内小场景环境中的无线接入设备，可借助固定宽带接入作为其回传手段，具有体积小、布点方便、快速覆盖、拆装简易等优势，在一定程度上弥补了传统建设手段周期长、受制于机房场地的短板，有效解决了目前部分楼宇传输接入和室内分布实施困难的问题。
除了此次上海联通把Femtocell引入厚重的历史保护建筑之外，2009年，天津联通利用Femtocell解决了另一种场景下的3G覆盖和容量难题，那就是高校校园的3G覆盖。
2009年初，天津联通启动全市的3G网络部署规划，考虑到3G的潜在用户群体中一个重要的组成部分就是高校学生，根据各种调查结论可以了解到，高校学生对时尚、新鲜的3G业务有着明显超出普通社会人士的兴趣，因此对这一类用户群体所在区域的3G网络覆盖和业务体验成为天津联通在网络规划部署时的关注热点。如图3所示。
如果采用传统的宏网络方式解决高校的网络覆盖，显然存在着几个问题，一是基站站址选择费时费力，成本高昂，且宿舍等室内场景下的覆盖质量难有保证。另外高校学生所在的校园内用户密度很高，学生对移动数据业务的使用需求也非常大，总的看来，宏蜂窝网络很难解决室内覆盖和数据业务容量这两个难题。
综合考虑3G网络覆盖的需求和现实困难，天津联通和华为合作，花了不到两个月的时间，采用Femtocell解决方案完成对天津多所高校的宿舍区域进行3G覆盖。2009年5月17日。天津联通首先在天津大学、南开大学正式Femto预商用网络，一期项目覆盖了两所高校的两栋宿舍楼，共应用了约100合Femtoeplco(Femto企业级ap节点)，覆盖学生人数2000佘人，有效解决了在校学生超大流量、高并发率的高速数据业务使用需求。随后，天津联通与华为联合完成了Femtocell校园网二期建设，选择了天津六所高校进行校园全部宿舍覆盖。
从各种渠道得到的消息来看，通过Femto解决方案实现3G网络的高校校园覆盖，在全球范围内属于首次，该项目也于2009年10月获得了第四届全国信息化应用、通信技术创新优秀成果奖金奖。
(3)快速实现重要场馆业务体验保障，Femto小材大用
2010年2月初，在天津市西青区某酒店，成功举行了由天津市经济和信息化委员会举办、天津联通协办的“天津市信息化建设座谈会”，此次会议期间，天津联通向来自全市的政企领导、行业合作伙伴、重要客户展示了一系列3G和移动互联网业务，wCDma／HSpa提供的高带宽、大容量的业务体验给与会人员留下了良好的印象。
天津联通计划在会议期间向与会者现场演示利用iphone手机和HSpa数据卡接入互联网，为了保证最佳的业务演示效果，经过天津联通与华为的商讨，确定了用Femtoceil方案来解决网络覆盖和网络容量问题。双方利用酒店的光纤和五类线配线系统，不涉及任何走线、电源改造等繁杂任务，数小时即完成在业务演示区部署Femtocell基站，并完成各种业务的调试和优化，为会议的召开提供了一个高效、低成本、体验良好的支撑网络。
3 Femtocell产业即将腾飞，中国联通有望扮演关键推动力量
由于系统成熟度、设备价格以及商业模式不明等多种因素。2009年之前整个行业基本处于设备功能验证阶段。全球首个3GFemtocell商用网络诞生于2008年12月初的新加坡StarHub，由华为独家提供系统设备和家用基站。2009年，华为、阿尔卡特朗讯、picoChip、airvana等供应商陆续推出了可商用的Femtocell商用系统解决方案及更加小巧的家用基站，对高速数据业务、与宏网络的切换、融合业务的支持更加满足运营商和消费者的需求，运营商对Femtocell的心态更加积极，陆续启动Femtocell的测试验证和小规模商用。
随着Femtocell产业链的进一步成熟，业界普遍预测2011年将是Femto产业真正腾飞的一年，咨询研究机构aBiResearch预测。到2011年底，全球Femtoell用户将超过2000这个级别，2010年-2014年复合增长率达101％。在使用场景和用户细分上，以Consumer(家庭用户)为主，enterprise(中小企业办公场所)以及用于metro(城域宏网络)覆盖补充的场景从2011年也开始快速增长，如图4所示，预计2014年全球不同场景下的Femto用户将分别达到：家庭(1.09亿)、中小企业(1300万)、城域覆盖(1510万)，合计1.37亿，相对于enterprise和metro市场，Consumer(家庭用户)是Femtocell的用户市场主体，约占80％左右。
数学建模覆盖问题篇6
关键词：无线传感器网络；覆盖优化；粒子群算法；虚拟力算法
中图分类号：tp18文献标识码：a文章编号：1009-3044（2015）28-0036-04
ResearchonCoverageoptimizationalgorithmofwirelessSensornetworkBasedonparticleSwarmoptimization
Linwei-jian，HaoYon-tao
（CaDResaerchCenteroftongjiUniversity，Shanghai201804，China）
abstract：themainresearchofworksinthepaperisthecoverageoptimizationproblemofwirelesssensornetworkbasedonthemobilenode.Firstly，establishirregularsensemodelaccordingtothecharacteristicsofsensorsandsensingregion，andestablishawirelesssensornetworkcoverageoptimizationmodelbasedonandmaximumcoveragewithminimumnodemovingdistance.Combinedtheparticleswarmoptimization（pSo）withthevirtualforcealgorithm，weproposedparticleswarmalgorithmbasedonchangingaccelerationfactorparticleswarmoptimizationbasedonvirtualforce（VFCapSo）.Comparisonandanalysistheresultsofthealgorithm，wefoundthealgorithmchangingaccelerationfactorparticleswarmoptimizationbasedonvirtualforce（VFCapSo）isbest.
Keywords：wSn；coveragecontrol；particleswarmoptimization；virtualforce
无线传感器网络（wirelesssensornetwork，wSn）是由一组小功率受限且具备传感和通信功能的节点组成。在无线传感器网络的各种应用中，网络覆盖是一个重要的衡量标准，它决定了传感器网络对覆盖区域的监测效果。合理的节点部署策略，不仅能够提高对目标区域的覆盖效果，也能有效利用传感器网络的资源，提高能量利用率，延长网络寿命。
在实际的应用过程中，可以通过部署可移动的节点来应对地形环境、部署方式等限制。当检测到网络未达到预定的覆盖效果时，计算一个新的位置并将节点移动到该位置，弥补覆盖漏洞从而提高覆盖率。同时，考虑到传感器节点一旦部署，往往很难获得可靠连续的能量供应，如何通过优化部署策略，减少移动过程中的能量消耗也是重要的一个方面。本文针对包含移动节点的无线传感器网络，设计一种优化的部署策略，使得无线传感器网络在多种因素的制约之下，能够合理的部署无线传感器节点的位置。这对于优化资源分配，最大限度的覆盖目标区域，保障网络正常高效工作，延长网络的使用寿命具有非常重要的意义。
1研究现状
国内外许多学者相继提出了针对移动传感器网络的覆盖优化问题算法：Howard，Zhou等人首度将势场理论应用于传感器网络的覆盖控制，通过假设虚拟势场和虚拟受力，利用物理学定律指导网络的布局优化过程[1]。在传感器经过最初的随机放置之后，使用虚拟力算法（VFa）作为传感器部署策略，可以以提高覆盖面。文献[2]提出了一种用于无线传感网络布局优化的粒子群优化策略。该策略采用概率测量模型评价网络测量性能，以网络有效覆盖率为优化目标，通过粒子群算法搜索全局最优布局方法。文献[3]将粒子群算法和混沌算法相结合，求解以移动传感节点位置为输入参数网络覆盖面积为目标的无线传感器网络覆盖优化问题。文献[4]提出了一种基于遗传算法的移动无线传感器网络中节点再部署方法，利用多目标优化对网络的覆盖率和节点的移动距离进行优化，从而延长了网络的生命周期。
2无线传感器网络模型
2.1无线传感器网络节点感知模型
常用的节点感知模型包括以下三种：二元感知模型、概率感知模型[5]和不规则感知模型[6]。针对基于移动节点的传感器网络优化部署，为了更加贴近无线传感器网络的实际工作情况，本文采用文献[6]提出的不规则感知模型，采用如下定义计算传感器节点的感测概率：
[Ss，p=0，dsi，p>Rpe-ξds，p-Rc，Rc≤dsi，p≤Rp1，dsi，p
式中[ξ]表示衰减因子，视具体的部署场景以及传感器功率和类型而定。[Rc]表示可信半径，在此半径内能够100%地监测到物理事件。[ai]为节点在第[i]方向上可变半径系数。[Rp]表示最大半径，大于[Rp]则无法感测到物理事件。[dsi，p]表示[Si]和[p]之间的欧几里得距离，即传感器[Si]部署在点[xi，yi]上，[x，y]中的任意点[p]，[dSi，p=xi-x2+yi-y2]。
不规则感知模型在某些特殊情况下可以转换为二元感知模型和概率感知模型。当[Ri=Rp]时，不规则感知模型退化成了二元感知模型，检测半径[x=Ri=Rp]。而当设置所有感测方向上的不规则感知半径为理论最大感测半径，即上述[ai=1，i=1，2，3…n]时，不规则感知模型退化成了简单的概率感知模型。
2.2无线传感器网络覆盖优化模型
2.2.1度量标准
1）覆盖率度量
覆盖率定义为受到检测的区域大小与整个目标区域大小的比值。关于覆盖率的计算，我们通过网格来实现：将受检测区域划分为大小相等的网格，计算每个网格点受到检测的概率，统计检测概率大于某一值的网格数量进而计算出目标区域的覆盖率。
对于某个网格，我们将它被整个监测区域中的所有传感器节点检测到得概率定义为联合检测概率[13，15]，网格p的联合检测概率如下公式所示：
[CpSall，p=1-i=n1-CpSi，p]
式中[Sall]表示测量目标点的传感器节点集合，[CpSi，p]为传感器[Si]对目标点[p]的感知概率。
令[Cth]为目标点能够被检测到的概率阈值，则目标点能被有效检测到的条件为：
[minxpypCpSall，p≥Cth]
若网格点i被覆盖，则令标志位[Cov_flagi=1]，否则[Cov_flagi=0]。则算法覆盖率定义如下：
[Cov=i=1nGCov_flagi/nG]
nG为在感兴趣区域划分的网格总数[7]。
2）节点移动距离度量
在移动过程中需要考虑目标区域中所有节点的移动总能耗。假设节点变换位置时都按照直线方式移动，而移动能耗与移动距离成正比，因此该问题转化成了节点的移动距离之和。可以将度量标准表示如下[3]：
[Dis=i=1kdi]
其中[di]表示传感器节点[Si]从初始部署位置移动到最终位置的距离。
2.2.2优化目标函数
本文提出的综合考虑覆盖率和移动距离的目标函数如下：
[e=maxf1?Cov+f2?1DisnL+1]
其中，Cov表示覆盖率计算公式，Dis表示传感器节点移距离，n表示目标区域部署的传感器节点数量，L表示目标区域为L*L的矩形区域的边长，F1表示覆盖率优化目标所占的权重，F2表示移动距离优化目标所占的权重。
实验证明，该公式能够适应覆盖范围以及节点数目的变化，在目标范围变化后不需要调整权重就能达到预先设置的优化目标。
3粒子群算法解决无线传感器网络覆盖优化问题
3.1粒子群算法介绍
粒子群算法（particleswarmoptimization，pSo）是由Kennedy和eberhart于1995年提出的一种优化算法[8，9]。pSo算法中每个粒子代表了解空间中的一个解，粒子依据同伴及自己的搜索经验来动态调整自己的搜索位置和速度。
在一个规模为n的粒子群中，粒子i（i=1，2，…，n）将根据下面的公式来更新自己的速度和位置[10]：
[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi），Xi=Xi+Vi，]
式中[xi]表示第[ii=1，2，3…n]个粒子的当前位置，[Vi]表示第[ii=1，2，3…n]个粒子的当前速度，pBest[i]表示粒子i所经历过的历史最优位置，pBest[g]表示网络中所有粒子经历过的最优位置，rand（）、Rand（）表示[0，1]上的随机数，[ω]表示惯性权重（inertiaweight），取值为0.8，c1、c2是个两个常数，称为学习因子。本文设置c1=c2=1，使得粒子具有相同的全局和局部搜索能力。
3.2粒子编码
在实际应用当中，粒子的编码分为两部分，一部分是粒子的位置，一部分是粒子的速度。假设传感器网络中有n个节点，每个节点都有X、Y两个位置坐标，网络对目标区域的覆盖率作为决策变量，也就是说传感器节点最优部署位置的维数空间为2n，所以将粒子编码设计成一个大小为2n的向量。向量中的每一个分量表示某个传感器节点的X或Y方向的位置。
单个粒子位置的编码设计为：
[X=X1，Y1，X2，Y2……Xn，Yn]
那么单个粒子在空间中的飞行速度编码的设计为：
[V=VX1，VY1，VX2，VY2，……VXn，VYn]
整个粒子群中所有粒子采用相同的位置和速度编码，并且每个粒子的位置和速度向量单独计算。
3.3适应度函数
以覆盖率最大并且节点移动距离最小为目标函数的优化方案，其适应度函数为：
[fitness=f1?Cov+f2?1DisnL+1]
3.4算法流程
第一步初始化各个参数
根据配置初始化算法参数、模型参数以及传感器节点属性。
第二步初始化粒子群
初始化粒子群的方法：目标区域的范围[posmin，posmax]内，选取2n随机数构成n个传感器节点的初始位置（x，y），并以这个初始位置构成的向量初始化整个粒子群中所有粒子的位置向量。粒子群中所有粒子的位置向量均为[X=X1，Y1，X2，Y2……Xn，Yn]。对于粒子的速度来说，粒子速度的初始化值均为0。粒子群中所有粒子的速度向量均为[V=VX1，VY1，VX2，VY2，……VXn，VYn]。
第三步根据粒子适应度函数计算各粒子的适应度值
使用上文提到的适应度计算方法计算某个粒子的适应度函数值。
第四步迭代更新粒子的速度和位置
当算法运行到第n次迭代时，比较所有粒子搜索到的历史最优位置pBest[i]，i=1，2，…n，并取最好位置来更新全局最优位置gBest。在第k+1次迭代，所有粒子的位置和速度按照位置更新方程和速度更新方程进行更新。在更新的过程中，粒子在每一维上的飞行速度的上下限为Vmax和Vmin；粒子在每一维上的位置的上下限位posmax和posmin。
第五步循环迭代，判断是否满足终止条件
满足终止条件时，停止迭代，输出全局最优位置；否则，循环迭代，转入第三步。一般设置最大迭代次数作为算法的终止条件。
4改进的粒子群算法解决无线传感器网络覆盖优化问题
文献[11]通过类比的手法，引入物理学中的库伦力和万有引力的模型，提出了一种基于虚拟力的覆盖优化方法。但是此算法并不适合于网格模型：当网格面积过小且数量很多，即感知精度较高的时候，往往会使得某块未覆盖的区域内包含过多的小网格，每个网格都对附近的节点产生引力，从而使得传感器节点收到的引力过大导致过快的运动，错过了需要覆盖的区域。
本文针对不规则感知模型的复杂性，在上述虚拟力算法的基础上进行了改进，避免了因网格面积过小而网格数量过大产生的引力叠加问题，并成功与粒子群算法相结合，提出了一种基于虚拟力的粒子群算法来求解无线传感器网络覆盖优化问题。
4.1改进虚拟力模型
首先，目标区域被分成许多个面积相等的小网格，将目标区域的覆盖转化为对小网格的覆盖，未覆盖的小网格对附近的传感器节点具有吸引力，使算法能够将节点移到未覆盖的区域，增加覆盖率。将未覆盖点对传感器的吸引力定义为：
[Fik=riskdik2，ri
其中，[Fik]为第K个未覆盖的网格对传感器节点i产生的引力，[dik]为两者之间的距离，[ri]定义为传感器节点的可靠感知半径，[Ri]为传感器节点的通信半径，而[Sk]为第K个未覆盖的网格的面积。
为避免多个传感器节点的覆盖区域产生重合，定义了两个节点之间具有斥力。将两个传感器节点之间的虚拟力定义为：
[Fij=rirjdij2，dij
其中[dij]为传感器节点之间的距离，[Ri，Rj]为两个传感器的通信半径，[ri，rj]为两个传感器的感知半径，两个传感器收到大小相等方向相反的作用力与反作用力。
4.2结合粒子群算法
粒子编码同标准粒子群算法一致，唯一不同的是为每个传感器增加了虚拟力。通过将粒子群算法中单个粒子的速度和位置更新公式改进如下，使得粒子群算法和虚拟力算法相结合：
[Vi=ω*Vi+c1*rand（）*（pBest[i]-Xi）+c2*Rand（）*（pBest[g]-Xi）+c3*Fi，Xi=Xi+Vi，]
速度更新公式的前半段和标准粒子群一样，主要不同是增加了虚拟力部分c3*Fi，可以理解为使用粒子受力产生的加速度来更新粒子的运动速度。其中c3为虚拟力加速因子，与c1、c2的值比较接近，c3过大很有可能导致粒子受力过大飞过未覆盖点，Fi为节点i受到的X或Y方向上的合力，Vi为该粒子的第i维速度。本文中c3取值为0.4。
由于虚拟力对粒子更新位置有积极的指导作用，所以算法收敛速度较快，但是在算法后期由于虚拟力的存在，粒子在进行局部搜索的时候会被虚拟力阻碍，往往无法搜索到更优的解。因此本文对上述虚拟力加速因子c3进行动态调整，在算法初期保持c3具有较大的一个值，并随着迭代次数的增加，c3逐渐减小。其更新公式为：
[c3=c3begin+g×c3end-c3begingmax]
c3在开始的时候取值为0.5，在结束的时候取值为0.2。在算法前期主要发挥虚拟力算法的优势，使得算法尽快地进行收敛，粒子单独搜索整个解空间，在算法后期减小虚拟力的影响，发挥粒子群算法的优势，重点对全局最优解附近的解空间进行精确搜索，找到更优解。
仿真结果显示，结合虚拟力的动态线性调整惯性权值和加速因子的粒子群算法（VFCapSo）迭代速度以及最大覆盖率均优于标准粒子群算法，取得了比较好的效果。
5算法仿真和测试
本节使用的不规则感知模型参数设置如下：
传感器节点可靠感知半径为18，最大可感区域为30，通信半径为40，节点一共有180个方向，每个方向上在可靠感知半径和最大可感区域内被分成10块区段，衰减因子为0.05。
相关设置以及节点的效果图具体如图1所示：
算法的运行结果如图3，分别为适应度每代最大，以及每代适应度最大所对应的节点移动距离，每代适应度最大所对应的覆盖率。
6结束语
本文采用了文献[6]中提出的不规则感知模型，并建立了综合考虑覆盖率和移动距离为目标的数学模型，验证了以覆盖率和移动距离为目标的数学模型能够在保证覆盖率的前提下有效减少节点的移动距离。将粒子群算法应用到无线传感器网络覆盖优化问题中去，并对已有的算法进行了改进，成功地将自适应调整惯性因子的粒子群算法（apSo）、混沌粒子群算法（CpSo）、线性调整加速因子的粒子群算法（CapSo）应用到无线传感器网络覆盖优化中去，并结合虚拟力算法提出了基于虚拟力的动态调整线性加速因子的粒子群算法（VFCapSo）、基于虚拟力的粒子群算法（VFpSo）和基于虚拟力的遗传算法（VFGa）算法，经过仿真实验验证了新算法的有效性。通过比较分析，有效的验证了虚拟力算法对算法性能的提升，同时验证了本文提出的三种结合虚拟力算法中VFCapSo性能最好，同时适用于覆盖率最大为目标和综合考虑覆盖率和移动距离为目标的优化模型。
参考文献：
[1]ZouY，ChakrabartyK.Sensordeploymentandtargetlocalizationbasedonvirtualforces[J].ieeesocieties，2003，2（1）：293-303.
[2]林祝亮，冯远静.基于粒子群算法的无线传感网络覆盖优化策略[J].计算机仿真，2009，26（4）：190-193.
[3]刘维亭，范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用，2011，31（2）：338-340.
[4]南国芳，楠.基于进化优化的移动感知节点部署算法[J].电子学报，2012，40（5）：1017-1022.
[5]刘维亭，范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用，2011，31（2）：338-340.
[6]赵小敏，毛科技，何文秀，等.感测范围不规则情况下无线传感器网络节点部署算法[J].软件学报，2012，23（1）：59-68.
[7]王伟，林锋，周激流.无线传感器网络覆盖问题的研究进展[J].计算机应用研究，2010，27（1）：32-35.
[8]ShiY，eberhartR.amodifiedparticleswarmoptimizer[C].in：ieeeworldCongressonComputationalintelligence，1998：69-73.
[9]冯翔，陈国龙，郭文忠.粒子群优化算法中加速因子的设置与试验分析[J].集美大学学报：自然科学版，2006，11（2）：146-150.
数学建模覆盖问题篇7
关键词wLan；热点覆盖；优化；方式
中图分类号：tn929文献标识码：a文章编号：1671-7597（2014）14-0194-01
生活的进步，技术的发展，使wLan运用越来越普遍，对于整个城市而言，wLan的建设置至关重要。它的热点选取和优化是wLan信号最关键的环节。由于网络用户群不断的扩大，局部网络的运用也随之增大。例如：校园和政府、企业等但单位。wLan的运营由多个商家组成，可能会出现网络互相干扰的现象，为了避免热点网络共存引起网络信号不稳定的现象发生，就需要对它进行分流，加以规划。减少网络信号不稳定对用户带来不便，努力提高用户的体验值。网络市场中互联网的份额占有率基本由移动互联网和电信这两个运营商占据，而移动互联网络数据流量占有的比例较大，占市场份额的70%，电信却只占了30%。所以，移动互联网络对互联网流量的影响最大。针对这一问题，运营商必须采用分流技术对网络进行流量分流，加大网络的容量，降低网络建设的成本，wLan可以为窝蜂网络承载提供前，实现网络的无限延伸，也可以帮助3G网络实行分流。
1wLan热点特征及其建设模式
waLn建设的关键主要是热点类型的选取和数据流量的分流，需要对这两点加以分析，如果wLan的热点使用的情况相对靠前的。依据网络的数据流量和它热点类进行统计，以前两百名作为参考点。根据分析可知，排在前面的政府、学校、医院、运营商、专门市场和就酒店者六个需求量大，占用数据流量较高，加大wLan的建设的压力。用户对网络质量的要求越来越高，wLan建设就需要更一步加强。由于用户群的不同热点，区域网络数据流量的平均值也不一样，所以，wLan的建设时，要根据区域的特点来选取合适热点场景进行建设，把相同热点网络类型进行归类，有规则有料理的进行建设和管理，如果用户的需求低或是密度小，可以根据现场的实际情况进行网络设置，若果用户需求的密度大，需求量较高，可实行热点覆盖建设。建设时可分三步行进行：1）分阶段；2）分层次；3）分场景。在建设时坚持统一化原则，按步骤实施。有效的提高wLan业务，把wLan业务发展和定位看作是网络规划的终极目标。
2wLan的覆盖模式
2.1wLan的完全覆盖模式的内涵
wLan的覆盖在我国市场上大致分几种模式，针对城市的规划，城市可以采用“完全覆盖模式”对城市进行无缝隙网络覆盖。这样城市用户就可以无时无地的体验网络带来的便捷了。所以，城市无线网的建设是wLan发展的最终目标。但由于“完全覆盖模式”发展不够成熟，网络的频率、网络传输还有待改进，加大了建设的成本。“完全覆盖模式”主要考虑的因素：1）如何实现网络的无缝隙完全覆盖，怎样充分利用wLan和无线宽带的优势弥补3G、2G的不足，真正实现无缝切换，提高用户的依赖度；2）Sim卡是流量消费的主要来源，该怎么进行基肥，需要根据不同的区域来设计。
2.2分区域覆盖模式的含义
“分区域覆盖模式”就是按核心区域、旅游区域、住宅区来进行划分的，再对其进行wLan覆盖。这些区域的用户群较大，需要保证网络的流畅性。把网络数据流量进行分流，可以确保网络区域覆盖的流畅性。而“分区域覆盖模式”也存在着很多不足，需要改善。它依据用户群的不同根据特点进行wLan覆盖，针对覆盖方式的不同，计费上也可以进行适当的调节。运营商可以针对不同的区域进行不同套餐的设置。按用户的需求进行套餐价格的定制以满足各个层次的用户需求。
2.3热点覆盖模式的内容
“热点覆盖模式”是指：在特定场所小范围区域进行wLan覆盖。例如：麦当劳、肯德基、大型商场、奶茶店、面包店等场所，由于网络的流动性强覆盖的信号较差，用户量比较大且连续性差，往往使用户不能高效低的体验网络的流畅性。针对“热点覆盖模式”需要考虑的问题是：1）在一定范围内保证网络信号的强度，满足临时用户对网络的需求，调高用户对网络的信赖度；2）wLan用户为热点区域网络使用打下了基础，利用专线接入技术为公司、校园等场所提供优质的网络服务，保证用户高速的体验网络。网络的高质量服务，合理的收取网络所产生的费用也有了依据；3）把相同的热点类型进行分层建设，专门制定针对客户群的热点营运模式进行网络的设置，尽量保障做到最优惠的价格享受最优质的网络服务。要注意wLan金蛇时的盲区，要合理的按步骤建设，从以热点覆盖为主，再到日后的“以点到面”的建设，慢慢发展。建设初期，最重要的是做好网络的正常运行，才能确保收益。网络建设要逐步归规划，渐渐完善。根据数据流量的需求和特征，采用“区域覆盖模式”在大范围片区进行wLan覆盖，真正实现高速无线宽带网络和3G中速无线宽带网络的无线城市建设。
3无线城市的建设要对wLan热点选择
确保无线城市有效的建设，必须针对热点覆盖的面积进行选择，做到最好最高速的网络建设，对已有的热点要及时的进行调整和优化。根据城市的网络环境和网络状态制作流量分布图，对网络进行规划、建设、设计、调整、优化。如果在使用较高的数据流量区域内，必须从实地勘察后才能进行热点的选取。设wLan热点的作用，它可以在高数据流量区域转换用户使用网络，进行分流，提高网速速度，满足广大用户的网络需求。因此数据流量分流作用在wLan建设中必不可少，要继续寻找有可能存在的新的流量潜力的站点。建设和选取热点的工作要确切落实和维护调整，保证用户网络的稳定，杜绝网络的不连续性发生。由于wLan热点的存在流动性问题，就需要及时对站点进行更新建设，以便于进行及时的检查、更建、评估，改善wLan建设热点质量，加快wLan覆盖的脚步。通过网络技术，对wLan进行实施跟踪调查，以便于及时做好应急措施，抢修网络信号等状况。保持信号的稳定性及其连续性，减少掉线率，保障用户顺畅上网，结合3G网管模式对wLan的数据流量进行比较，分析数据流量，取长补短，明确3G、wLan网络对用户的分流中起到的作用，并及时调整wLan的热点的覆盖。
4结束语
时代的发展，网络的需要，使无线城市的建设迎来了一轮又一轮发展高潮，而wLan建设是无线城市建设中重要一环，想要wLan在无线城市建设中起到关键作用，就需要强化wLan热点建设和选取，让它日趋完善成熟，最终实现覆盖大部分重要区域的无线宽带网络。
参考文献
数学建模覆盖问题篇8
关键词：无线网络学生宿舍接入要求覆盖方式
中图分类号：tn929.53文献标识码：a文章编号：1007-9416（2013）05-0047-02
现代高校校园网有线网络建设已逐渐普及和趋于成熟，广大在校生和教职工的学习、生活和工作已经离不开网络，近年来，加快完善校园网的信息化建设已经是高校的重要工作之一。随着网络的普及，人们越来越要求尽可能方便、快速、移动式的使用网络，同时，带有无线功能的笔记本电脑、平板电脑、智能手机等无线客户端产品逐渐普及，而传统的有线网络有地域限制的局限，显然将不能满足人们的移动式使用需求。无线局域网（wLan）技术作为一项新兴的网络技术，开始逐步被应用于高校网络建设中。
本文结合华南理工大学广州学院新建学生宿舍无线网的建设实际，探讨高校校园网无线网络的部署方案，主要就无线网络的覆盖问题和部署方式展开讨论，希望能够给同类院校提供一些参考。
1无线网络覆盖的主要问题
无线接入由于其接入方式的特殊性，决定了其必然无法避免盲区、干扰、隐藏节点等问题。
1.1无线盲区
无线覆盖，特别是室外覆盖室内时，由于天线角度、ap功率等因素，有可能在某一区域（特别是楼的两端）出现盲区，无线信号很弱，甚至无法找到SSiD的情况。即使是室内覆盖方式，如果天线部署位置不适合，也会出现盲区问题。通常解决无线盲区的方式是补点，增加设备来进行盲区的覆盖。
1.2无线干扰的产生
由于无线传输路径难以控制，会出现折射、反射等多种情况，同时信号传输也会存在衰耗，这些都直接影响了接入点的信号质量。
1.3无线信号衰减
无线信号在无线传输过程中会因传输介质等因素引起的能量损失。空间中的超高频和微波波段信号的传播，也会对信号带来多种传输损伤、衰减和多径衰落。无线传播损伤有衰减、失真、自由空间损耗、噪声、大气吸收和折射等。多径衰落是由于无线信号从发射机到接收机的传输过程中，由于障碍物的影响，信号经过折射、反射等途径，在时间和相位上发生变化，相比直接传输信号产生衰落。信号衰减是无线信号穿过障碍物信号强度变弱。障碍物不仅影响ap到无线客户端的无线信号，同时也会影响无线客户端到ap的无线信号。
表1为障碍物的衰减经验数据表：
无线信号经过障碍物会有衰减，这点在高密覆盖时可以利用来减小ap的覆盖范围，避免不同ap间的干扰。
1.4同频干扰
无线干扰是wLan接入点设备（ap）或无线客户端受到其它相邻wLanap与无线客户端以及在同一无许可限制的频带中运行的非802.11设备的干扰。由于空口资源有限，同频干扰会降低本信道的吞吐量。在实际应用中，发现在学生宿舍主要还是来源于其它ap的同信道干扰。其它诸如微波炉等干扰相对较少。
1.5隐藏节点
隐藏节点的前提条件是存在同频干扰。由于wLan系统使用的是CSma/Ca公平信道竞争机制，在这个机制中，Sta在有数据发送时，首先监听信道，如果信道中没有其它Sta在传输数据，则首先随机退避一个时间，如果在这个时间内没有其它Sta抢占到信道，Sta等待完后可以立即占用信道并传输数据。但在无线网络中，并不是连接在同一个ap下的节点彼此都是可见的。如下图所示，节点a、B、C都工作在同一个信道上，当节点a向节点B发送分组时，载波侦听机制无法阻止节点C发送数据，造成信号在节点B处冲突。节点C是隐藏在节点a的覆盖范围之外的、却又能对节点a的发送形成冲突的节点，这种在发送节点覆盖范围以外的、存在着潜在冲突的节点问题就是信道访问中的隐藏终端问题。隐藏终端问题会大大降低信道的通信能力。直接造成的后果就是：某些节点使用p2p业务的时候，大量占用了带宽资源，造成其它用户不能和ap连接，或者与ap联接后掉线、失去ip地址。（图1）
除了Sta互相隐藏之外，还有可能ap之间也可能隐藏，造成Sta无法正常接收数据的情况。
2宿舍楼无线网络接入要求
华南理工大学广州学院学生宿舍楼的建筑结构通常为6层楼，每层楼分两排（如图2）每排约25个房间。
2.1接入密度要求
一层楼每行楼道25个宿舍，每个宿舍内有4名学生，按照25%的开通并发率，则每排楼层接入用户数为50人。按照无线ap的接入能力（每ap接入15人最佳），则每个楼层需要部署4个ap。
2.2业务要求
包括internet访问和校内（教育网）资源访问。其中internet为主要业务，细分为网游、QQ、p2p/网页浏览、在线视频等。其中网游是宿舍内的主流业务。根据实际统计，网络中小包（
2.3无线部署方式
实际应用中，宿舍覆盖有三种模式：（1）室外覆盖室内；（2）室内小功率ap覆盖；（3）室内分布式覆盖。
2.4室外覆盖室内
由于学生宿舍楼建筑通常比较有规律，一般都是多个宿舍楼平行排列，因此有些运营商愿意采用这种室外覆盖室内的方式。在对面的宿舍楼上部署天线覆盖本宿舍楼，同时本宿舍楼部署天线覆盖对面宿舍楼。
这种方式部署起来比较简单，施工容易，使用的设备相对较少。但是问题也较多。
首先，由于室外覆盖，很容易受环境的影响，室外的树木、雨雪天气都会影响无线传输的性能。增加了网络维护难度。
其次，室外覆盖方式很难达到高密的要求。在6层楼，每层楼单面25个房间，每个房间4个学生情况下，即使只考虑25%的接入并发率，也需要接入90个用户，由于每个ap接入用户量约为15个，那么也需要部署6个ap。对于一个60米长（每层10个房间时楼长约为60m）的范围内部署6个ap，这意味这必然存在相同信道覆盖同一个楼，即使采用方向性很强的天线，由于反射等原因，也难以避免同频干扰；而由于一个ap覆盖了1-6层楼，必然带来隐藏节点众多的问题，会大大降低无线的的传输性能，而隐藏节点越多，性能下降越厉害，容易导致网速慢，用户无法连接等现象。
最后，部署中天线的放置位置也很难确定，虽然在3楼位置覆盖对面最为合适（不易产生盲区），但带来的反射也最为严重，很容易产生两栋楼之间的彼此多次反射，实际应用中发现这种方式带来的同频干扰非常严重且很难解决。而且两个楼面对面的天线间即使信道不同，若楼距离较近，也容易产生饱和失真。
综上所述，室外覆盖室内方式不适合高密情况下的宿舍楼覆盖，若仅是作为有线接入网的补充，则可以考虑这种覆盖方式，但是ap部署密度要小（比如一个楼面采用1-2个ap覆盖），并且允许存在盲区。
3室内小功率ap覆盖
这种覆盖模式应用较多。通常都是ap通过功分连接部署在楼道的全向吸顶天线，每个ap覆盖6-8个宿舍。一层楼部署约3-4个ap。
保证信道合理部署，相同信道尽量远离。同一楼层信道分布如图3所示。
楼层间信道分布如这种覆盖方式，可以有效的进行全方位覆盖，避免盲区的出现。
3.1同频干扰
这种部署模式下，特别是在一个楼道4个以上ap情况下，或者在楼层隔板对无线信号衰减不大的情况下，很容易出现同频干扰问题。因此，适当降低ap功率是必须的，若楼层隔板衰减很小的情况下，需要考虑将ap/天线部署在宿舍内，通过宿舍的墙壁来衰减无线信号，避免对其它楼层的影响。
3.2隐藏节点
实际上，不管怎么部署，想完全规避隐藏节点几乎是不可能的。但可以通过部署优化来减少隐藏节点的数量，减轻隐藏节点带来的不良影响。通过信道规划和ap降低功率，将隐藏节点控制在一个ap覆盖范围内，减少隐藏节点数量。避免性能大幅度降低。
4室内分布式覆盖
数学建模覆盖问题篇9
【论文摘要】:针对汽车覆盖件冲压的有限元模拟方面的具体问题进行了研究,采用弹塑性有限元的数值模拟及试验研究的方法,对汽车覆盖件拉延过程中的成形进行了研究。针对拉延模拟结果进行应力应变分析,寻找工艺参数的优化方案,改进的工艺方案使破裂情况明显改善。
由于冲压工艺具有生产效率高、质量稳定、成本低以及可加工复杂形状等一系列优点,在机械行业的应用非常广泛,占有十分重要的地位[1]。但是冲压模具的设计主要依据工程师长期积累的经验。对于复杂的成形工艺和模具,设计质量难以得到保证;一些关键性的设计参数要在模具制造出来之后,通过反复的调试、修改才能确定。这样就浪费了大量的人力、物力和时问[2-3]。随着有限元技术和计算机技术的发展,数值模拟已逐渐成为工艺分析及优化设计的有效工具。
1.有限元模型的建立和参数设定
一般汽车覆盖件工艺设计流程具体分析如下:(1)根据产品图及产品冲压工艺设计,进行详细的车身产品工艺性分析。为了实现拉延或创造良好的拉延条件,必须合理考虑冲压方向、工艺补充部分形状以及压料面形式、拉延筋布置等重要工艺因素。其中包括利用计算机进行的工艺补充面三维设计。(2)在满足产品使用的前提下,将过剩的质量要求及时反馈给产品设计部门,进行研讨,力争把产品完善到最简单、最合理的工艺要求,以克服产品的过剩质量,减少不必要的工装投入。(3)利用计算机进行车身产品的冲压工艺性分析,进行图面形状的分析探讨和尺寸公差的分析研究,在充分理解、把握产品使用性能要求的前提下,考虑用户使用和维修,利用塑性加工原理、冲压工艺知识和模具设计结构的有关知识,设计冲压工艺过程图。在设计过程中,同时要分析冲压工艺方案,发现不足之处,进行必要的修正。(4)模具设计人员按照冲压工艺过程图的基本要求进行模具设计,模具CaD设计包括上、下模座,工作部分零件,导向部件,定位零件和进出料装置等设计。数控编程和模型人员按照冲压工艺过程图和模具图进行数控编程和模型制造,最后按照冲压工艺过程模具图要求进行机械加工和模具装配调试,最终调试出合格的产品。
选用某轿车内部地板零件产品图,此零件是一个比较复杂的中小型车身结构件。由于零件拉延深度深,并且具有局部反拉延,因此成形过程估计会出现问题,为了验证问题所在我们利用Cae软件进行模拟成形计算。对于复杂冲压零件的成形过程,不但同一时刻不同位置的板坯所承受的变形方式和变形程度不同,而且不同时刻同一位置的板坯所承受的变形方式和变形程度也不同;另外,冲压工艺边界条件的设定对变形路径和各部分的变形程度的影响也非常明显。
一般划分网格时,首先建立一个拓扑结构模型。这一步骤是连接分离的型面,使你可以在网格划分的时候得到连续的网格(两个相连的元素在分界线之问共同享用相同的节点)。系统能通过你所定义的公差自动辨认普通表面之问的分界线,以建立我们所说的拓扑模型。建立好拓扑结构以后,应定义网格划分的参数,并进行网格的自动划分。一般情况下要求用户最少确定四个参数,包括最小元素大小,最大元素大小,两个相连的元素之问的法向夹角,网格的弦高。最小元素的大小影响着网格划分中最小元素的尺寸。当模型的型面比较平坦时它最大元素的大小则受最大元素参数的影响。两个相连的元素之问的法向夹角所起的作用是规定了两个相连元素之问的最大法向夹角,即当两个元素的夹角大于用户给定的值时,这两个元素会分裂为更多的元素,故它影响着倒角和小圆角部分的网格密度,它的值越小网格则越密。例如:一般我们在划分模具网格时,它的拉延圆角最好有五行元素,这时调整法向夹角的参数就可以达到目的。弦高的大小则影响着大网格半径表面上的网格密度,它的值越大,则网格越少。在汽车覆盖件模拟中,板料数据一般都是曲线,因此板料的网格划分与模具的划分不一样。
根据实际需要确定板料特性,应力应变关系=537(0.0102+)0.23mpa,法向各项异性系数为1.8。其他参数如下:扬氏模量2.07e+5mpa;屈服极限210mpa;泊松比0.28;板材厚度0.8mm;板料质量密度7.83e-9;r0=1.87,r45=1.27,r90=2.17。由于摩擦系数必须有实验得出,特别是几种常用材料在工业生产中的实际摩擦系数。考虑到汽车覆盖件生产厂家和模具生产厂家的实际,一般不考虑使用油,在拉延前要使用清洁防锈油清理兼。因此我们必须通过试验来得出在几种不同条件下的摩擦系数,例如干摩擦和加清洁防锈油后的摩擦。还有就是拉延筋的拉延阻力在不同形状拉延筋情况下的取值。测定为此我们设计了覆盖件模具的摩擦系数和实际拉延筋拉延阻力的测定的试验,详细试验结果在第六章中。摩擦系数根据测量结果给定0.175,拉延筋选取单圆筋,拉延阻力为0.178Kn/mm。
2.汽车覆盖件冲压的有限元模拟结果分析
经过计算后,板料的FLD如图2所示。在FLD图中,红色表示破裂,粉红色表示起皱,而在应变云图中红色表示正应变,深蓝表示副应变。从FLD图中我们可以看出四处破裂,分别是大鼓包处,凹坑底部,最下方的小鼓包处,右上方的直壁处。通过主应变和次应变云图可以看出在突起的鼓包顶端处为双向拉应变发生破裂,并目_从板料轮廓的变化发现在有拉延筋的地方板料儿乎没有流动,形成过度胀形,凹坑底部破裂处也同样出现胀形过度问题。而模具拉延直壁处的破裂却是不同形式的,该处的主应变为拉应变,次应变为压应变,为明显的拉深破裂状态。之所以只有这个直壁角破裂是因为这个角离大鼓包最近,并且通过成形过程的模拟我们发现这个直角壁首先成形,从而在凹坑成形前破裂。其它四个角由于拉延高度低并且没有复杂的凸凹变形,都有足够的板料流动量,板料的流动情况良好,所以没有破裂。
3.汽车覆盖件冲压工艺改进方案
在去掉拉延筋,变化压边力后还是无法缓解,于是决定改变模型,我们把拉延直壁消除降低了模具拉延高度;把型面中那一个接近大直角型面过渡改为一个小缓坡,减缓了陡峭程度;由于模具进料困难,所以去掉拉延筋,然后设定压边力为400Kn,摩擦系数为0.12,进行模拟后如图4所示。可以看出与未改前的情况有很大的不同,破裂情况明显改善,尤其是右上角直壁处的破裂变得很小,这是由于降低了它的拉延高度。
4.结论
世界上每年的钢材有半数以上被轧制成板料和管料。金属板、管的成形和加工在航空、航天、汽车、船舶及许多民用工业中都占有相当重的比例。因此,提高相应的成形技术和制造水平是一个具有普遍意义的大课题。因此,文章在汽车覆盖件数值模拟和试验研究的基础上,采用有限元的数值模拟及试验研究的方法,对汽车覆盖件拉延过程中的成形进行了数值模拟和试验研究。
参考文献
[1]李东升,黄小明,胡世光.汽车覆盖件拉延筋的单元模拟试验研究[D].北京航空航天大学学报,1995.21(2):67-71.
数学建模覆盖问题篇10
针对传感器提供的信息不可靠导致的节点部署问题，研究了4种不同的静态无线传感器网络（wSn）部署形式，并将这4个组合优化问题归纳为np完全问题，提出了一种基于动态规划的不确定性感知节点部署算法进行求解。算法首先为感兴趣区域内的传感器节点找到其最佳的K个部署位置，然后从K个部署位置中选择最优部署方案。该算法能够在保证覆盖范围和连接性的前提下确定最小数量的传感器及其位置。仿真实验结果表明，相对于当前最新的其他传感器部署策略，所提算法在均匀覆盖、优先覆盖要求以及网络连接性下的性能都更优。
关键词：
无线传感器网络；节点部署；np完全问题；动态规划；节点数目
0引言
综合了无线通信技术、传感器技术、嵌入式计算技术和分布式信息处理技术的无线传感器网络（wirelessSensornetwork，wSn），是目前国际上前沿热点的研究领域。传感器部署问题作为无线传感网络的一个基本问题，近年来引起广泛关注[1-4]。实际上，在感兴趣区域（Regionofinterest，Roi）部署的传感器数量及其位置，决定了网络的拓扑结构，进而影响网络诸多内在属性，比如覆盖范围、连接性、成本及运行寿命等。因此，一个无线传感网络的性能很大程度上取决于传感器的部署。本文主要针对高效的传感器节点部署算法进行了研究，本文工作原创性贡献有：1）将静态无线传感网络部署问题描述为4种具体情况。2）根据基于证据的传感器覆盖模型，提出了四种不确定性感知部署算法：Se2BDa（simplifiedalgorithmofefficientevidencebasedsensordeploymentalgorithm）、e2BDap（efficientevidencebasedsensordeploymentalgorithmpreferentialcoverageobjective）、e2BDaC（efficientevidencebasedsensordeploymentalgorithmpreferentialnetworkconnectivityobjective）和e2BDa。其中，Se2BDa确定最小数目的传感器及其位置来保证区域完整均匀覆盖。e2BDap、e2BDaC、e2BDa均考虑了Se2BDa中的目标因素；另外e2BDap考虑了优先覆盖区域目标因素，e2BDaC考虑了网络连接性目标因素，而e2BDa既考虑了优先覆盖区域又考虑了网络连接性。3）通过仿真实验验证了本文方法能够进行基于不确定性感知的传感器高效部署。
1相关工作
传感器节点部署问题是目前无线传感网中的研究热点，相继有众多的研究者提出了一系列用于节点部署的方案。例如，张荣标等[5]针对多跳无线传感器网络的漏斗效应问题，提出了基于簇负载平衡的冗余节点部署算法（RedundancynodesDeploymentalgorithm，RnDa）。RnDa采用分簇结构平衡簇内能耗，并根据各簇负载情况配置一定数量的冗余节点以平衡簇际能耗。该算法把节点下一跳选路概率作为边模糊权值引入模糊图论，提出了用于计算数据从源节点经m跳到达目的节点概率的到达率定理。仿真结果表明，RnDa既能明显延长网络寿命，又能有效平衡网络中节点能耗。孙伟等[6]将节点部署问题建模为一个组合优化问题，以网络覆盖率为目标函数，提出了一种基于人工鱼群与微粒群的混合算法的无线传感器网络节点部署优化策略；仿真实验结果表明，提出的算法减少了迭代次数，并且提高了网络覆盖率，相对于人工鱼群算法和微粒群算法来说能取得更好的效果；温俊等[7]提出了保证覆盖率和网络生存期的最少节点部署问题；基于传感器网络的数据传输特性，从提高能量效率和降低剩余能量的角度提出了节点数递减的重叠放置方法和节点密度递减的随机部署方法。两种新部署方法比已有部署方法需要的节点数少，剩余能量低，因而提高了能量利用率。仿真实验表明，两种新部署策略的能量效率是已有方法的3～4倍。
另外还有，王力立等[8]研究了感知能力异构的传感器节点部署问题。给出了节点部署优化问题的整数线性规划模型，并指出这个问题是np完全的。提出了近似但计算有效的贪婪优化部署算法，通过找出最佳部署位置、传感器类型和感知方向，实现网络的优化配置。仿真结果表明，该算法可以降低网络配置成本和工作节点数，具有较好的优化部署效果。Senouci等[9]提出了一种基于不确定性感知的传感器覆盖模型。该模型更接近现实，可以更好地处理包括传感器可靠性在内的各种传感器部署问题。本文在Senouci等工作的基础上，进一步考虑了约束条件：优先覆盖范围和网络连接性能。提出了一种基于证据的传感器高效部署算法（e2BDa），该算法是一种多项式时间部署算法，以动态规划理论为基础。e2BDa能够确定最小的传感器数量及其位置来同时保证覆盖范围和连接性。
2问题描述
本文把传感器部署问题分为四个阶段。在第一阶段，只考虑传感器均匀覆盖和成本，给出了部署问题的正式定义并且给出e2BDa的简单版本——Se2BDa，其中优先覆盖和连接性能两个因素被弱化。在第二个和第三个阶段，以第一阶段理论为基础，分别考虑优先覆盖和连接性能两个目标因素，这样本文又得到两种不同的网络部署策略e2BDap和e2BDaC。最终，在第四阶段，本文把所有目标因素综合考虑（例：优先覆盖范围、成本和连接性目标），最终版本的策略称为e2BDa。下面将详细阐述。
本文把Roi看成二维或三维网格。调整网格粒度（即相邻两点距离），可以改变计算复杂度及精度。为了简便，本文只讨论二维情况。把Roi看成m×n网格。每小格中心点可能是传感器或者目标点的位置，如图1所示。
2.1以均匀覆盖及成本为目标
在本文的第1个wSn部署问题上，在满足所有点连接性需要的同时传感器的数量必须最低。本文假定均匀覆盖，每一点p∈Roi都有相应的最低事件检测概率阈值th；因此本文首个部署问题可以被定义为：对点p∈Roi，所测得的事件检测pignistic概率Betp（{θ1}）必须大于或者等于th，或者用数学形式表达为：
2.3以均匀覆盖、成本以及连接性为目标
在第3个wSn的部署问题上，本文将在第1个问题基础上加上连接性这一目标。本文的目标是：建立wSn，在优化其部署成本的同时，保证均匀覆盖和网络连接性。
为了保证网络的连接性，连通图G=（V，e）必须连通，其中：V是各部署传感器构成的点集，e是边集。假定采用传输磁盘模型[1]，可以使用单位磁盘图来描述网络。CCG表示G=（V，e）的已连接组件集合，其中CCG的基数必须等于1，以保证网络的连接性。第3个问题可以被定义为以下形式：
2.4优先覆盖、成本和连接性目标
在第4个部署问题中，本文以第3个部署问题为基础，加入优先覆盖这一目标。本文的目的是：部署wSn，优化部署成本，同时保证优先覆盖及网络连接性。该问题可以表达为：
需要指出的是，使用优先部署限制条件可以轻松地对不规则Roi区域进行建模。此时，本文使用一个包括Roi区域的规则网格，对于不属于Roi的点p，令thp值为0。
3传感器部署策略
第2章提出的4种关于部署优化的问题是np完全问题，本章采用一种基于多项式时间和动态规划的全面方案来解决前面所提所有问题。首先，考虑一个简单版本e2BDa，即Se2BDa，来解决第一个问题；其次，本文讨论如何解决优先覆盖问题，并给出e2BDap部署策略；第三，本文引入网络连接性，给出第三种部署策略e2BDaC；最后，本文把所有目标因素放在一起考虑，给出部署策略e2BDa。
3.1均匀覆盖和成本
用动态规划方法处理部署问题的第一步就是确定最优解的结构。本文所要解决的问题的最优子结构如下：假定n个传感器s1，s2，…，sn的最佳部署策略为op。那么op范围内n（n
可以利用子结构子问题的最优解来获得整个问题的最优解。然而，对于这一部署问题，各种子问题的总数量的输入大小是个指数，这将让本文的算法成为指数时间算法。于是，本文采用多项式时间算法来求得次优解。
定义S为所有传感器集合，s表示部署在p点的单个传感器。当传感器部署在p点时，本文用SCp来表示Roi各点证据的对应矩阵。SCp与各网格点均有关联，SCp的计算参考文献[9]的工作。
假定n个传感器s1，s2，…，sn的部署策略为Dn，如果满足方程（3），则p点被覆盖。本文用scoreDn表示“虚假”融合中心做出的覆盖决策数量，“虚假”融合中心是根据部署策略Dn及Roi区域s1，s2，…，sn部署传感器集合提供的证据而做出覆盖决策的。再部署一个传感器sn+1，那么会生成新的部署策略Dqn+1，其中q表示新部署传感器sn+1的位置，求得的scoreDqn+1可以纳入pSpS是矩阵的名字吗？矩阵。
开始时，本文考虑Roi内的一个传感器s1，面对网格空间可能的所有位置，算法计算相应的pS矩阵，并将s1的k个最佳部署位置存储起来，用Bp表示。k可看成是可取任意值的输入参数。然后，在每一步i中，本文在网格上寻找si的可能位置，并获得相应的pS矩阵（此时s1至si-1传感器已经部署完毕）。Bp被不断更新，以保存为s1，s2，…，si找到的k个最佳部署位置。由于本文的目的是确保每一个网格点均被覆盖，因此该预期输出是首个中止准则。本文定义传感器可用数目（numberofavailableSensors，naS）为第二个中止准则。在最后一步，算法从Bp为s1，s2，…，sn传感器找到的k个最佳部署位置中选择最优部署方案，其中n≤naS。Se2BDa伪代码见算法1。
有必要指出的是，信任函数是组合操作的中性元素，Se2BDa在计算覆盖区域时并没有对所有格点进行检查，而是采用一种滑动窗口策略，检查了部分区域。如果naS很大，Se2BDa的计算复杂度为o（kw2mn），其中：k是每次迭代时考虑的最佳部署位置个数，而w表示窗口尺寸。事实上，w值取决于传感器覆盖模型，并且等于传感器的传感范围Rs；乘积kw2用常数C表示，则Se2BDa的计算复杂度等于o（Cmn）。
3.2优先覆盖范围
对于每个点p∈Roi，都有一个对应的事先定义好的最低事件检测概率阈值thp。如果pignistic概率θ1大于thp，则点p∈Roi被覆盖。或者说，如果Betp（{θ1}）≥thp，则p∈Roi被覆盖。本文以第1个问题为基础，加入优先覆盖目标因素，由此得到的算法称为e2BDap。在Se2BDa中本文没有假定均匀覆盖。因此只需考虑与假设θ1对应的pignistic概率，就能处理优先覆盖问题。e2BDap使用一个检测阈值矩阵th作为输入参数来代替Se2BDa中的单值th，除此之外，e2BDap与Se2BDa完全相同。
3.3网络连接性
如前面一样，本文以Se2BDa为基础加入网络连接性目标，得出的算法为e2BDaC。Se2BDa部署算法为增量算法，因此为连接性提供了本质保证。在每一步i中，使用Bp发现所有可用网格点pa∈Roi及位于已部署传感器s1，s2，…，si-1连接范围内的网格点。本文将这些点表示为{pac}。同时假定G′=（V′，e′）是利用e2BDaC算法已部署传感器s1，s2，…，si-1的连通图。G′是连通图。设Si是部署在pa点的新传感器，G″=（V″，e″）是新生成的连通图。pa点必须保证G″是连通的。
与Se2BDa相比，e2BDaC考虑了{pac}网格点而不考虑{pa}网格点此处描述矛盾，请作相应调整。。传输范围Rc作为e2BDaC的一个输入参数。
3.4同时考虑优先覆盖和网络连接性
要同时处理优先覆盖和网络连接性目标因素，本文以前述方法为基础，将e2BDap和e2BDaC融合在一起，进而得出e2BDa算法，其伪代码见算法2，其计算复杂度为o（Cmn）。
4仿真实验
为了评估e2BDa算法的有效性，本文对e2BDa和最新部署算法（包含maxavgCov[11]、maxminCov[11]、min_miSS[12]和eBDa[9]）进行对比。为了使评估的结果更为公正，对maxavgCov、maxminCov、min_miSS算法进行改进，使其也采用基于证据的覆盖模型。最近一些相关算法在本文性能评估时加以忽略，比如说文献[13]中的BDa，该算法即使多次迭代也无法实现全覆盖。
本文进行3步模拟：在第1步中，本文在均匀覆盖要求下比较不同部署策略性能；第2步中，在优先覆盖要求下比较不同部署策略性能；第3步中，在网络连接性要求下比较不同部署策略性能。假设Roi为正方形，其边长为n个单元格。在第1～2步中，设定Rc值较大以放松网络连接性要求。仿真参数（以网格点为单位）见表1。
4.1均匀覆盖
本文首先在3种均匀覆盖场景下对不同部署策略进行性能评估。三种场景下的th值分别为0.65，0.8，0.95，表2给出保证全均匀覆盖需要的传感器数量。
从表2中可以首先观察到，对各种部署策略，部署的成本随着覆盖范围增加而增加；其次，eBDa和e2BDa使用的传感器数目远小于另外三种部署策略。同时，e2BDa性能优于eBDa；当覆盖范围较大时，e2BDa相对eBDa的性能优势更加明显。
4.2优先覆盖范围
在这个部分，本文研究当不同区域有不同覆盖要求时各种部署策略性能。文献[9]根据多元正态分布实现优先覆盖要求，如图2所示。
4.3网络连接性
在这个部分，本文在网络的连接性要求下对不同部署策略进行性能比较。必须指出的是，除了e2BDa外，其他4种分布策略均未考虑网络连接性问题。本文在不同Rc值下，检测了不同分布策略生成网络的拓扑结构连通图，表4总结了实验结果。
当Rc等于4时，所有分布策略都能保证网络连接性，这是因为网络连接性与覆盖范围间有一定关联。文献[14]中，作者利用二元传感器覆盖模型对这一关联进行了研究，并证明了当Rc≥2Rs时，传感器覆盖范围可以保证网络连通性。基于证据的传感器覆盖范围模型条件下网络连接性和覆盖范围分析，不在本文讨论范围内。在本实验中，当Rc等于1时，只有e2BDa能保证网络的连接性。本文同时注意到，此时e2BDa部署成本比第一步要高，高出的成本是为了满足网络连接性要求。只有e2BDa在所有场景下都能保证网络的连接性。