• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 15
    • 下载费用:30 金币  

    重庆时时彩定位胆计划: 用于宽区域监视的有限数量传感器的合理布置的方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN200880011503.1

    申请日:

    2008.02.14

    公开号:

    CN101711390A

    公开日:

    2010.05.19

    当前法律状态:

    终止

    有效性:

    无权

    法律详情: 未缴年费专利权终止IPC(主分类):G06F 17/50申请日:20080214授权公告日:20130109终止日期:20160214|||授权|||专利申请权的转移IPC(主分类):G06F 17/50变更事项:申请人变更前权利人:特尔科迪亚许可公司有限公司变更后权利人:TTI发明有限责任公司变更事项:地址变更前权利人:美国新泽西州变更后权利人:美国特拉华州登记生效日:20120516|||实质审查的生效IPC(主分类):G06F 17/50申请日:20080214|||公开
    IPC分类号: G06F17/50 主分类号: G06F17/50
    申请人: 特尔科迪亚许可公司有限公司
    发明人: H·卢斯
    地址: 美国新泽西州
    优先权: 2007.02.16 US 60/901,909; 2007.03.20 US 11/725,794
    专利代理机构: 上海专利商标事务所有限公司 31100 代理人: 张政权;谢喜堂
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN200880011503.1

    授权公告号:

    |||101711390B|||||||||

    法律状态公告日:

    2017.03.29|||2013.01.09|||2012.06.27|||2010.07.07|||2010.05.19

    法律状态类型:

    专利权的终止|||授权|||专利申请权、专利权的转移|||实质审查的生效|||公开

    摘要

    将有限数量的传感器布置在所选位置以便实现对需要监测的所有位置的合理覆盖等级。提供给任何具体位置的覆盖等级取决于监测该位置的所有传感器和该传感器的特性,传感器特性包括物体检测概率和错误警报的概率。这些概率可取决于监测和被监测的位置。通过得到覆盖等级的字典式最大向量来获得对所有位置的合理覆盖,其中这些覆盖等级以非降序分类。该方法生成字典式极大极小最优化模型,其解提供合理覆盖等级。为了便于计算,生成非线性整数最优化模型,其解提供与字典式极大极小最优化模型相同的覆盖等级。

    权利要求书

    1: 一种用于确定有限数量的传感器在指定区域中的最优布置的方法,其中传感器的最优位置向所述区域内的所有位置提供合理覆盖等级,包括以下步骤: (a)生成指定区域的网络表示,所述网络表示包括节点和有向链路,其中每个节点表示将被监测的子区域或可布置传感器的子区域或将被监测且可布置传感器的子区域,且其中每个有向链路表示节点对之间的监视关系,其中节点对包括其中可布置传感器的节点集合中的第一节点和将被监测的节点集合中的相关联的第二节点; (b)根据传感器的特性表征传感器,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于不同的节点对可以不同; (c)针对提供给将被监测的每个节点的覆盖等级生成监视性能函数,作为监测每个将被监测的节点的传感器的位置的函数; (d)生成合理传感器位置模型作为字典式极大极小最优化模型,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给被监测节点的以非降序分类的覆盖等级,其中所述解提供合理覆盖等级;以及 (e)生成所述字典式极大极小最优化模型,作为非线性整数最优化模型,所述模型的解向所有节点提供合理覆盖等级,其中通过现有最优化方法计算所述解。
    2: 一种用于确定有限数量的传感器在指定区域中的最优布置的方法,其中传感器的最优位置向所述区域内的所有位置提供合理覆盖等级,包括以下步骤: (a)生成指定区域的网络表示,其包括节点和有向链路,其中每个节点表示将被监测的子区域或可布置传感器的子区域或将被监测且可布置传感器的子区域,且其中每个有向链路表示节点对之间的监视关系,其中节点对包括其中可布置传感器的节点集合中的第一节点和将被监测的节点集合中的相关联的第二节点; (b)根据传感器的特性表征传感器,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于不同的节点对可以不同; (c)针对提供给将被监测的每个节点的覆盖等级生成监视性能函数,作为监测每个将被监测的节点的传感器的位置的函数; (d)生成合理传感器位置模型ESLM作为字典式极大极小最优化模型,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给被监测节点的以非降序分类的覆盖等级,其中所述解提供合理覆盖等级;以及 (e)生成所述字典式极大极小最优化模型,作为非线性整数最优化模型,所述模型的解向所述区域内需要被监测的所有位置提供合理覆盖等级,其中通过求解ESLM-EX计算所述解。
    3: 如权利要求2所述的方法,其特征在于,ESLM是字典式极大极小最优化模型,且对象函数指定字典式最大向量,所述向量的元素是对被监测子区域的以非降序分类的覆盖等级,且限制条件指定布置的传感器的数量的极限,且决策变量表示传感器布置决策。
    4: 如权利要求2所述的方法,其特征在于,所述节点包括表示将被监测的子区域的节点集合N,节点集合S表示可布置传感器的位置,且从集合S中的节点至集合N中的相关联节点的链路指示集合S中的所述节点能够监测N中处于节点对中的所述相关联节点。
    5: 如权利要求4所述的方法,其特征在于,监视性能函数计算提供给集合N中任何指定节点的覆盖等级,作为布置在可监测集合N中的指定节点的集合S中的节点处的所有传感 器的函数。
    6: 如权利要求5所述的方法,其特征在于,所述监视性能函数用作传感器的输入特性,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于所述节点集合N和S中的每个节点对可以不同。
    7: 如权利要求2所述的方法,其特征在于,非线性整数最优化模型ESLM-EX根据ESLM生成,且ESLM-EX的最优解向被监测的所有节点提供合理覆盖范围。
    8: 如权利要求7所述的方法,其特征在于,通过应用已知的最优化方法生成ESLM-EX的最优解。
    9: 一种用于确定有限数量的传感器在节点集合S中的最优布置的方法,所述最优布置向节点集合N中的节点提供合理覆盖等级, (a)根据传感器的特性表征传感器,所述特性包括物体检测的概率和错误警报的概率,其中每个节点对具有其相关联的概率; (b)针对提供给集合N中的每个节点的覆盖等级生成监视性能函数,作为布置在监测集合N中的相关联节点的集合S中的节点处的传感器的函数; (c)生成模型ESLM作为字典式极大极小最优化模型,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给集合N中的节点的以非降序分类的覆盖等级,且所述解向集合N中的所有节点提供合理覆盖等级;以及 (d)生成模型ESLP-EX,通过现有的最优化方法计算所述模型的解,从而向集合N中的所有节点提供合理覆盖等级。
    10: 如权利要求9所述的方法,其特征在于,从一个周期到下一个周期中所述传感器中的至少一个的位置改变。
    11: 如权利要求10所述的方法,其特征在于,在每个周期中,利用可能的传感器位置的修正集合求解ESLP-EX。
    12: 一种用于确定有限数量的传感器在指定区域中的最优布置的系统,其中传感器的最优位置向所述区域内的所有位置提供合理覆盖等级,包括: (a)生成指定区域的网络表示的装置,所述网络表示包括节点和有向链路,其中每个节点表示将被监测的子区域或可布置传感器的子区域或将被监测且可布置传感器的子区域,且其中每个有向链路表示节点对之间的监视关系,其中节点对包括其中可布置传感器的节点集合中的第一节点和将被监测的节点集合中的相关联的第二节点; (b)根据传感器的特性表征的多个传感器,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于不同的节点对可以不同; (c)针对提供给将被监测的每个节点的覆盖等级生成监视性能函数的装置,所述监视性能函数作为监测每个将被监测的节点的传感器的位置的函数; (d)生成合理传感器位置模型作为字典式极大极小最优化模型的装置,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给被监测节点的以非降序分类的覆盖等级,其中所述解提供合理覆盖等级; (e)生成所述字典式极大极小最优化模型作为非线性整数最优化模型的装置,所述模型的解向所有节点提供合理覆盖等级,其中通过现有最优化方法计算所述解;以及 (f)根据所述字典式最优化模型的解布置的所述多个传感器。
    13: 一种用于确定有限数量的传感器在指定区域中的最优布置的系统,其中传感器的最优位置向所述区域内的所有位置提供合理覆盖等级,包括: (a)生成指定区域的网络表示的装置,所述网络表示包括节点和有向链路,其中每个节点表示将被监测的子区域或可布置传感器的子区域或将被监测且可布置传感器的子区域,且其中每个有向链路表示节点对之间的监视关系,其中节点对包括其中可布置传感器的节点集合中的第一节点和将被监测的节点集合中的相关联的第二节点;根据传感器的特性表征的多个传感器,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于不同的节点对可以不同; (b)针对提供给将被监测的每个节点的覆盖等级生成监视性能函数的装置,所述监视性能函数作为监测每个将被监测的节点的传感器的位置的函数; (c)生成合理传感器位置模型ESLM作为字典式极大极小最优化模型的装置,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给被监测节点的以非降序分类的覆盖等级,其中所述解提供合理覆盖等级; (d)生成所述字典式极大极小最优化模型作为非线性整数最优化模型ESLM-EX的装置,所述模型的解向所有节点提供合理覆盖等级,其中通过现有最优化方法计算所述解;以及 (e)所述多个传感器被布置成向所述区域内需要被监测的所有位置提供合理的覆盖等级,其中所述最优解是ESLM-EX的解。
    14: 如权利要求13所述的系统,其特征在于,ESLM是字典式极大极小最优化模型,且对象函数指定字典式最大向量,所述向量的元素是对被监测子区域的以非降序分类的覆盖等级,且限制条件指定布置的传感器的数量的极限,且决策变量表示传感器布置决策。
    15: 如权利要求13所述的系统,其特征在于,所述节点包括表示将被监测的子区域的节点集合N,节点集合S表示可布置传感器的位置,且从集合S中的节点至集合N中的相关联节点的链路指示集合S中的所述节点能够监测N中处于节点对中的所述相关联节点。
    16: 如权利要求15所述的系统,其特征在于,监视性能函数计算提供给集合N中任何指定节点的覆盖等级,作为布置在可监测集合N中的所述指定节点的集合S中的节点处的所有传感器的函数。
    17: 如权利要求16所述的系统,其特征在于,所述监视性能函数用作传感器的输入特性,所述特性包括物体检测的概率和错误警报的概率,其中所述概率对于所述节点集合N和S中的每个节点对可以不同。
    18: 如权利要求13所述的系统,其特征在于,非线性整数最优化模型ESLM-EX根据ESLM生成,且ESLM-EX的最优解向被监测的所有节点提供合理覆盖范围。
    19: 如权利要求18所述的系统,其特征在于,通过应用已知的最优化方法生成ESLM-EX的最优解。
    20: 一种用于确定有限数量的传感器在节点集合S中的最优布置的系统,所述最优布置向节点集合N中的节点提供合理覆盖等级,包括: a.根据传感器的特性表征的多个传感器,所述特性包括物体检测的概率和错误警报的概率,其中每个节点对具有其相关联的概率; b.针对提供给集合N中的每个节点的覆盖等级生成监视性能函数的装置,所述监视性 能函数作为布置在监测集合N中的相关联节点的集合S中的节点处的传感器的函数; c.生成模型ESLM作为字典式极大极小最优化模型的装置,所述模型的解提供字典式最大排序向量,所述向量的元素是提供给集合N中的节点的以非降序分类的覆盖等级,且所述解向集合N中的所有节点提供合理覆盖等级; d.生成模型ESLP-EX的装置,通过现有的最优化方法计算所述模型的解,从而向集合N中的所有节点提供合理覆盖等级;以及 e.根据所述ESLP-EX模型的解布置的所述多个传感器。
    21: 如权利要求20所述的系统,其特征在于,从一个周期到下一个周期中所述传感器中的至少一个的位置改变。
    22: 如权利要求21所述的系统,其特征在于,在每个周期中,利用可能的传感器位置的修正集合求解ESLP-EX。

    说明书


    用于宽区域监视的有限数量传感器的合理布置的方法和系统

         相关申请的交叉引用

        本申请要求2007年2月16日提交的美国临时专利申请No.60/901,909的权益,其整个内容通过引用结合于此。?

        【发明领域】

        本发明涉及有限数量的传感器在所选位置的最优布置,以便对所有位置提供充分?;?。?

        发明背景?

        使用传感器提供对宽区域的有效监视变得越来越常见??悸强赡芊胖弥钊缯ㄒ?、生物制剂或化学物质的有害物体的特定区域。遍及该区域安置固定数量的传感器,其中这些传感器的每一个提供对该区域内一个或多个位置的观察。这些传感器的观察通过数据融合过程组合,以便评定物体是否实际存在于所观察的位置中的一个或多个中。因为可布置的传感器的数量有限,所以确定这些传感器的最优位置非常重要。在某些应用中,可安置很多传感器,但仅有限数量的这些传感器可同时激活。?

        传感器还用于入侵检测。抵抗入侵的防御对于?;ご笄颉嗨乒?、油气管线、类似核反应堆、大工业中心、军事基地等战略设施——是必须的。此外,最优地布置传感器是极其重要的,从而实现适当的?;だ吹挚箍赡艽硬煌较蚪咏鼙;で虻娜肭终?。?

        有关的话题集中在诸如应急室、消防队和警察局之类的应急设施的最优位置上。方便的是通过网络表示区域,其中每个节点表示一邻域,例如尺寸为100x100米的正方形?;チ欢越诘愕牧绰繁硎敬右桓鼋诘愕搅硪桓鼋诘愕目赡芤贫?,且链路度量表示端节点之间的距离(或行程时间)。典型的问题是将有限数量的应急设施布置在这些节点的子集中,使得从任何节点至最近设施的?距离(或行程时间)最小化。在本领域中这是一个公知问题,称为网络极小极大位置问题或顶点中心问题。在本领域中称为集合覆盖问题的有关问题使在节点的子集处安置设施的成本最小化,从而每个节点位于距离最近设施的指定距离(或行程时间)内。L.V.Green和P.J.Kolesar的题为“Improving?EmergencyResponsiveness?with?Management?Science(利用管理科学改进应急响应)”,Management?Science(管理科学),50,1001?1014,2004提出应急响应模型的现有技术状态。?

        根据网络极小极大位置问题的应急设施最优位置不是唯一的,因为可能存在向最差远离位置提供最好的可能服务的很多解。因此,找到应从所有的极小极大解中选出哪个解是吸引人的。W.Ogryczak的题为“On?the?LexicographicMinimax?Approach?to?Location?Problems(位置问题的字典式极小极大方法)”的European?Journal?of?Operational?Research?(欧洲运筹学杂志),100,566?585,1997提出一种找到位置问题的字典式极小极大解的算法。正如在极小极大网络位置问题中,任何特定位置由单个设施服务,具体地由最接近该位置的设施服务。在将提供给各位置的服务从最差到最好排序(按照距离最近设施的距离或行程时间)意义上,字典式极小极大解是最佳极小极大解,所得到的排序向量是字典式最小的可能排顺向量。这一解被称为合理解。?

        K.Chakrabarty、S.S.Iyengar、H.Qi和E.Cho的题为“Grid?Coverage?forSurveillance?and?Target?Location?in?Distributed?Sensor?Networks(在分布式传感器网络中用于监视和目标定位的栅格覆盖)”,IEEE?Transactions?on?Computers(IEEE计算机学报),51,1448?1453,2002将传感器位置问题用公式表达为使在节点的子集安放传感器的成本最小化的集合覆盖问题,从而每个节点均在距离指定数量的传感器的指定距离(或行程时间)内。?

        本发明集中在利用字典极大极小目标布置有限数量的传感器,以便实现所有位置的合理覆盖。提供给任何特定位置的覆盖等级可取决于监测该位置的多个传感器的位置以及传感器的特性。这是以上W.Ogryczak的论文的重大扩展,且该论文中所使用的方法不能扩展到求解由本发明解决的问题。H.Luss的题为“On?Equitable?Resource?Allocation?Problems:A?Lexicographic?MinimaxApproach(合理资源分配问题:字典式极小极大方法)”,Operations?Research?(运筹学),47,361?378,1999提供了各种合理资源分配模型和求解方法的阐述;然而它们都不能应用于本发明。?

        【发明内容】

        本发明集中在将有限数量的传感器布置在所选位置,以便实现对需要被监测的所有位置的合理覆盖等级。受监视的区域被表示为网络,其中节点表示位置且互连链路指示监视关系??悸墙诘鉰处的传感器。除监测节点j以外,从节点j至节点i的链路表示节点j处的传感器还可监测节点i。提供给任何特定位置的覆盖等级取决于监测该位置的所有传感器以及传感器的特性。传感器的特性包括当目标存在于特定位置时监测到该特定位置处的目标的概率和当目标不存在于同一位置时错误地监测到同一位置处的目标的概率。对于每个(i,j)节点对这些概率可以不同。?

        假设传感器的位置是指定的。给出这些位置,提供给每个位置的覆盖等级被计算出来??悸翘峁└庑┪恢玫拿恳桓龅母哺堑燃兜南蛄?,该向量的元素(即覆盖等级)以非降序分类。所有位置的合理覆盖等级被指定为字典式最大的这种覆盖等级排顺向量。本发明确定有限数量的传感器的最优位置,从而实现所有位置的合理覆盖等级。本发明生成合理的传感器位置模型,作为字典式极大极小最优化模型,其解对所有位置提供合理覆盖等级。当前的现有技术水平的最优化解算机不能直接求解所述字典式极大极小最优化模型。本发明生成非线性整数最优化模型,其解还对所有位置提供合理或近合理的覆盖等级。所述非线性整数最优化模型的解可通过已知最优化方法的自适应来获得,诸如动态编程和各种元启发式,包括模拟退火和禁忌搜索。传感器位置模型可以是静态(一次)情形或动态(多周期)情形中使用的系统的一部分。在动态情形中,传感器位置被周期性改变以防止对手获悉该位置。?

        当结合附图阅读以下描述时可更清楚地理解本发明。?

        附图简述?

        图1示出传感器位置模型的网络表示。?

        图2示出传感器位置模型的对分网络表示。?

        图3是用于确定对所有位置提供合理覆盖等级的传感器位置的方法的流程图。?

        详细描述?

        现在参照附图尤其是图1,示出表示受监视的区域的网络100的示例。该区域由六个节点101?106表示。三个传感器如黑色节点101、104和106所表示地定位。将根据本发明的教示确定传感器的最优位置。有向链路107?115表示监视关系。例如,107表示从节点101至节点102(由实线有向链路示出)和从节点102至节点101(由虚线有向链路示出)的监视关系。实线有向链路表示实际上节点101具有监测节点102的传感器。虚线有向链路表示如果将传感器布置在节点102则节点102可监测节点101。注意,例如,节点101处的传感器监测节点101、102、105和106,且节点101受节点101(传感器始终监测它所处的节点)和106处的传感器监测。?

        使用以下的符号:?

        N=需要被监测的节点的集合。N中的节点由i索引。在图1中,N={101,102,103,104,105,106)。在实际情形中,N可以很大,其中具体的值取决于区域大小和由节点表示的区域。例如,如果受监视的区域是10km?x?10km的正方形且每个节点表示100m?x?100m的正方形,则N=10000。?

        S=传感器可位于的节点的集合。S中的节点由j索引。?

        尽管在示例100中假设S=N,但集合N和S可以不同。?

        J(i)=S中可监测节点i的节点子集。集合J(i)包括具有定向到节点i的链路的所有节点加上节点i自身——如果i∈S。例如,在图1中,J(101)={101,102,105,106}且J(102)={101,102,103,106}。?

        本发明提供一种在可用传感器的数量有限时确定最优位置的方法。尽管假设各传感器相同,但位于节点j处的传感器向节点i提供的覆盖等级取决于传感器特性和指定的节点i和j。传感器特性通常通过以下概率指定:?

        pij=假设节点i处有物体,节点j处的传感器检测到节点i处的物体的概率。?

        qij=假设i处没有物体,节点j处的传感器错误地检测到节点i处的物体?的概率(错误警报)。我们假设qij<pij。?

        基于位于集合J(i)中的节点处的所有传感器确定提供给位置i的覆盖等级。传感器位置问题的最优解将是向N中的所有节点提供合理覆盖的解。稍后将定义合理覆盖解。?

        在图2中,示出传感器位置模型的不同的网络200表示的示例,其中该模型被示为对分网络。节点201?206是其中可布置传感器的节点集合S。这些节点对应于网络100中的节点101?106。传感器在网络200中位于节点201、204和206处(黑色节点),对应于网络100中的节点101、104和106处的传感器位置。节点201?206中的每一个在网络200的右侧被复制。因此,节点207是节点201的复制,节点208是节点202的复制等等。节点207?212表示需要被监测的节点集合N。尽管在该示例中集合N和S包括相同的节点(在网络100中作出相同假设),但不需要这样。如果S和N不相同,则S中的某些节点在N中可能不具有复制节点,且N中的某些节点在S中可能不具有相对应的节点。网络200中链路表示监视关系。因此,例如节点201具有分别至节点207、208、211和212的链路213a?d,且节点202具有分别至节点207、208、209和212的链路216a?d。这些链路具有明显的与网络100中的链路的一对一对应,且增加了从集合S中的节点至集合N中其复制节点的链路。注意,实线链路将带有传感器的节点连接至N中的相关节点且虚线链路将不带有传感器的节点连接至N中的相关节点。容易地从网络200中导出集合J(i),例如J(207)={201,202,205,206}。因此,在此示例中,节点207由节点201和206中的两个传感器监测。注意,J(207)唯一地对应于网络100中的J(101)={101,102,105,106},其中节点101由节点101和106处的两个传感器监测。?

        图3呈现用于确定对所有位置提供合理覆盖等级的传感器位置的方法300的流程图。?

         方法的输入准备(步骤301302)

        生成指定区域的网络表示(301),如上参考图1和2所说明的。网络中的节点数量取决于区域大小和由单个节点表示的区域。所需的精确度取决于特定应用。指定将影响监视的质量的传感器的特性的表征(302)。这些特性可包括但不限于概率pij和qij。尽管假设所有传感器是同一类型的,但注意这些?概率取决于传感器位置和所监测的位置。不同传感器位置的不同概率可由这些位置与节点i的不同距离或由这些位置与节点i之间的某些障碍引起。网络表示(或者是图1的网络100或者是图2的网络200)和传感器的特性是传感器位置模型的主要输入。?

         监视性能函数的生成(步骤303)

        该方法的目标是确定有限数量的可用传感器的最优位置。设?

        xj=决策变量。如果传感器位于节点j,xj=1,否则xj=0。设x是所有决策变量xj的向量,j∈S。?

        fi(x)=节点i的监视性能函数,i∈N。对于向量x的具体值,该函数的结果值也被称为提供给节点i的覆盖等级。注意,只有影响fi(x)的决策变量xj才是j∈J(i)的决策变量。?

        以下提供可能的监视性能函数的两个示例。本发明不限于这些具体的性能函数。?

         示例1

        假设所有的概率qij=0且0<pij<1。那么,用于节点i的监视性能函数作为x的函数可被设置成节点i处的物体将被至少一个传感器检测到的概率。这表示?

         <mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <munder> <mi>&Pi;</mi> <mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>p</mi> <mi>ij</mi> </msub> <mo>)</mo> </mrow> <mo>,</mo> </mrow>i∈N,其中<mrow> <munder> <mi>&Pi;</mi> <mi>&phi;</mi> </munder> <mrow> <mo>(</mo> <mo>&CenterDot;</mo> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mrow>

        指定x的fi(x)的值被称为提供给节点i的覆盖等级;fi(x)的值越大,提供给节点i的覆盖等级越好。注意还可将方程式(1)写为<mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <munder> <mi>&Pi;</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <msup> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>p</mi> <mi>ij</mi> </msub> <mo>)</mo> </mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> </msup> <mo>,</mo> </mrow>i∈N。?

         示例2

        假设所有的概率qij满足0<qij<pij。则,可由比率(1?pij)/(1?qij)估计用于检测位置i处的物体的位置j处的传感器的有效性;比率越小,传感器越有效。显然,如果qij约等于pij,则在节点j布置传感器来监测节点i是无用的,因为从该传感器收集的信息将不会提供任何有意义的信息。注意,<mrow> <munder> <mi>&Pi;</mi> <mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>p</mi> <mi>ij</mi> </msub> <mo>)</mo> </mrow> </mrow>是假设节点i处有物体,监测节点i的传感器均未检测到节点i处的物体的条件概?率,而<mrow> <munder> <mi>&Pi;</mi> <mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>q</mi> <mi>ij</mi> </msub> <mo>)</mo> </mrow> </mrow>是假设节点i处没有物体,监测节点i的传感器均未错误地检测节点i处的物体的条件概率。类似于方程式(1),可选择1减去这些条件概率的比来形成以下的监视性能函数。?

         <mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <munder> <mi>&Pi;</mi> <mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <mfrac> <mrow> <mn>1</mn> <mo>-</mo> <msub> <mi>p</mi> <mi>ij</mi> </msub> </mrow> <mrow> <mn>1</mn> <mo>-</mo> <msub> <mi>q</mi> <mi>ij</mi> </msub> </mrow> </mfrac> <mo>,</mo> </mrow>i∈N,其中<mrow> <munder> <mi>&Pi;</mi> <mi>&phi;</mi> </munder> <mrow> <mo>(</mo> <mo>&CenterDot;</mo> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mrow>

        注意还可将方程式(2)写为<mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mn>1</mn> <mo>-</mo> <munder> <mi>&Pi;</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>J</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </munder> <msup> <mrow> <mo>(</mo> <mfrac> <mrow> <mn>1</mn> <mo>-</mo> <msub> <mi>p</mi> <mi>ij</mi> </msub> </mrow> <mrow> <mn>1</mn> <mo>-</mo> <msub> <mi>q</mi> <mi>ij</mi> </msub> </mrow> </mfrac> <mo>)</mo> </mrow> <msub> <mi>x</mi> <mi>j</mi> </msub> </msup> <mo>,</mo> <mi>i</mi> <mo>&Element;</mo> <mi>N</mi> <mo>.</mo> </mrow>

        可使用各种其它的监视函数??悸蔷咛宓膇,且设x1和x2是两个向量,其中对于所有的j∈J(i),<mrow> <msubsup> <mi>x</mi> <mi>j</mi> <mn>1</mn> </msubsup> <mo>&le;</mo> <msubsup> <mi>x</mi> <mi>j</mi> <mn>2</mn> </msubsup> <mo>,</mo> </mrow>且对于至少一个j∈J(i),<mrow> <msubsup> <mi>x</mi> <mi>j</mi> <mn>1</mn> </msubsup> <mo><</mo> <msubsup> <mi>x</mi> <mi>j</mi> <mn>2</mn> </msubsup> <mo>.</mo> </mrow>监视性能函数应满足以下的特性:?

         特性(i)

        函数fi(x)随变量j∈J(i)增加,即<mrow> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>x</mi> <mn>1</mn> </msup> <mo>)</mo> </mrow> <mo><</mo> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>x</mi> <mn>2</mn> </msup> <mo>)</mo> </mrow> <mo>.</mo> </mrow>

         特性(ii)

        假设在x1和x2中为0的一些变量j∈J(i)在x1和x2中被设置为1,分别得到向量在x1+和x2+。然后,fi(x1?)?fi(x1)≥fi(x2+)fi(x2);即,fi(x)在xj,j∈J(i)的整数值上凹入。?

        注意,特性(i)和(ii)适用于方程式(1)和(2)。?

         合理传感器模型的生成?ESLM(步骤304)

        该模型用监视性能函数fi(x),i∈N公式表达。?

        设?

        f(n)(x)=以非降序分类的所有fi(x)’的向量,即,?

         <mrow> <msup> <mi>f</mi> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mo>[</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>,</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>,</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>,</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mrow> <mo>|</mo> <mi>N</mi> <mo>|</mo> </mrow> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>]</mo> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>3</mn> <mo>.</mo> <mi>a</mi> <mo>)</mo> </mrow> </mrow>

        其中:?

         <mrow> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>&le;</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>&le;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&le;</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mrow> <mo>|</mo> <mi>N</mi> <mo>|</mo> </mrow> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>.</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>3</mn> <mo>.</mo> <mi>b</mi> <mo>)</mo> </mrow> </mrow>

        P=可用传感器的数量,P<|S|。这些传感器被布置在节点集合S的节点子集中,每个节点至多一个传感器。不需要考虑P≥|S|的情形,因为它导致传感器被布置在集合S中的每个节点处的无价值问题。?

        合理解是提供字典最大向量f(n)(x)的解。称为ESLM的合理传感器位置模型被公式表达为字典式极大极小最优化模型。?

         ESLM

         <mrow> <msup> <mi>V</mi> <mi>f</mi> </msup> <mo>=</mo> <munder> <mrow> <mi>lex</mi> <mi>max</mi> </mrow> <mi>x</mi> </munder> <mo>[</mo> <msup> <mi>f</mi> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>]</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>4</mn> <mo>.</mo> <mi>a</mi> <mo>)</mo> </mrow> </mrow>

        从而?

         <mrow> <msup> <mi>f</mi> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <mo>[</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>,</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>,</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>,</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mrow> <mo>|</mo> <mi>N</mi> <mo>|</mo> </mrow> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>]</mo> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>4</mn> <mo>.</mo> <mi>b</mi> <mo>)</mo> </mrow> </mrow>

         <mrow> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>&le;</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>&le;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&CenterDot;</mo> <mo>&le;</mo> <msub> <mi>f</mi> <msub> <mi>i</mi> <mrow> <mo>|</mo> <mi>N</mi> <mo>|</mo> </mrow> </msub> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>4</mn> <mo>.</mo> <mi>c</mi> <mo>)</mo> </mrow> </mrow>

         <mrow> <munder> <mi>&Sigma;</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>S</mi> </mrow> </munder> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mi>P</mi> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>4</mn> <mo>.</mo> <mi>d</mi> <mo>)</mo> </mrow> </mrow>

        xj=0,1,j∈S。(4.d)?

        目标函数(4.a)得到字典式最大向量Vf,其中通过语句(4.b)和(4.c),该向量构成以非降序分类的监视性能函数fi(x)。限制条件(4.d)和(4.e)限制对P布置的传感器的数量,其中在集合S的每个节点处最多布置一个传感器。如上所述,在方程式(1)和(2)中给出监视性能函数的示例。ELSM与用于监视性能函数的具体形式无关,只要这些函数是增函数即可(步骤303中的特性(i))。?

         可执行的合理传感器位置模型的生成(步骤305)

        尽管ESLM提供了用于计算合理解的完整且精确的公式,但该公式不能直接通过已知的最优化方法来求解。?

        因为,如上所述,假设监视性能函数fi(x),i∈N中的每一个都是增函数且在xj,j∈J(i)的整数值上凹入(如在步骤303中由特性(i)和(ii)指定的),将通过求解相关的非线性整数最优化模型来获得合理解(字典式极大极小解)。注意,仅出于说明性目的给出方程式(1)和(2)中指定的监视性能函数;全部要求是这些函数满足步骤303中指定的特性(i)和(ii)。设K是任意的大参数。以下非线性整数最优化模型的解将向如ESLM公式表达的合理位置传感器模型提供合理解。新的模型被称为可执行的合理传感器位置模型(ESLP?EX)。?

         ESLM?FX

         <mrow> <msup> <mi>V</mi> <mi>K</mi> </msup> <mo>=</mo> <munder> <mi>min</mi> <mi>x</mi> </munder> <mo>{</mo> <munder> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>&Element;</mo> <mi>N</mi> </mrow> </munder> <mfrac> <mn>1</mn> <msup> <mrow> <mo>[</mo> <mi>&epsiv;</mi> <mo>+</mo> <msub> <mi>f</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>]</mo> </mrow> <mi>K</mi> </msup> </mfrac> <mo>}</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>5</mn> <mo>.</mo> <mi>a</mi> <mo>)</mo> </mrow> </mrow>

        从而?

         <mrow> <munder> <mi>&Sigma;</mi> <mrow> <mi>j</mi> <mo>&Element;</mo> <mi>S</mi> </mrow> </munder> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>=</mo> <mi>P</mi> <mo>,</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>5</mn> <mo>.</mo> <mi>b</mi> <mo>)</mo> </mrow> </mrow>

        xj=0,1,j∈S。(5.c)?

        其中ε是出于计算目的引入的任意小参数,以避免目标函数(5.a)中的无限项。当K很大时,ESLP?EX将提供合理解,或者等价的字典式极大极小解。假设f1(x)<f2(x)。则,步骤303中的特性(i)表明对于大K,目标函数(5.a)中i=1的项显著大于目标函数(5.a)中i=2的项。该自变量应用于N中的每对节点。步骤303中的特性(ii)表明目标函数(5.a)中的第i项的提高在x1增加到x1+时大于在x2增加到x2+时实现的提高。因此,对于足够大的值K,ESLM?EX的最优解将是非降序分类的性能函数值的字典式最大可行向量。注意即使是小的K值(例如,K≥4),期望ESLM?EX的解提供近合理解??赏ü匝槿范ㄊ实钡腒值。?

         合理解的计算(步骤306)

        本发明生成模型ESLM?EX,其解提供合理传感器位置模型的合理解,其中该解可通过各种现有技术水平的最优化方法来计算。这些方法包括,但不限于动态编程和诸如模拟退火和禁忌搜索的元启发式。T.Ibaraki和N.Katoh的书籍“Resource?Allocation?Problems:Algorithmic?Approaches(资源分配问题:算法方法)”,MIT出版社,剑桥,马萨诸塞州,1988,在部分3.2提供求解ESLM?EX的动态编程算法。C.R.Reeves(编辑)的“Modern?Heuristic?Techniquesfor?Combinatorial?Problems(组合问题的现代启发技术)”,Halsted出版社,John?Wiley出版,纽约,1993,在他的书中介绍了各种元启发式的指南,包括对模拟退火和禁忌搜索的指南。?

        ESLM?EX可在静态(单个周期)或动态(多个周期)环境中使用??悸嵌肪?,其中例如每15分钟从所有传感器收集数据且数据分析重复地显示没有物体存在于任何位置。然而,在某时间之后,例如,在一天之后,期望改变某些传感器位置使得对手不能得知传感器的位置。这可通过例如改变可能的传感器位置的集合S并重新求解ESLM?EX来完成??衫媚承┧婊≡穹桨秆≡窦蟂中的改变。在某些应用中,在S中的每个节点处安装传感器,然而,在每个时间点,由于操作限制,这些传感器中的仅P<|S|被激活。在这种应用中,通过重新求解ESLM?EX周期性地改变被激活的传感器的位置,其中?集合S利用某些随机化选择方案改变。?

        最后,假设数据分析显示物体存在于位置的子集处的关注,即节点子集N?当前处。然后可将ESLM?EX应用到包括N当前中的节点的展开的新网络表示,使得新网络中的每个节点将表示比原始网络小得多的区域。然后,ESLM?EX可得到合理解,以将有限数量的第二类型传感器——例如移动传感器布置在由新网络表示的区域中,以便收集对受怀疑的区域的更精确观察。?

        以上描述的算法和建模能够在诸如计算设备之类的指令执行系统、装置或设备上执行。算法本身可包含在计算机可读介质中,该介质可以是能够包含、存储、通信、传播或传输由诸如计算设备之类的指令执行系统、装置或设备使用或与诸如计算设备之类的指令执行系统、装置或设备结合使用的程序的任何装置。?

        尽管已经描述并示出了用于在所选位置最优布置有限数量的传感器的方法,以便实现对所有位置的合理覆盖等级,但本领域的技术人员显而易见的是在不背离仅由所附权利要求的范围限定的本发明的广泛教示和范围的情况下变形和修改是可能的。?

        

    关 键 词:
    用于 区域 监视 有限 数量 传感器 合理 布置 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:用于宽区域监视的有限数量传感器的合理布置的方法.pdf
    链接地址://www.4mum.com.cn/p-5781936.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03