Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2013年 第50卷 第3期    出版日期:2013-03-15
论文
无线传感器网络中基于超宽带的TOA/AOA联合定位研究
肖 竹 谭光华 李仁发 张小明
2013, 50(3):  453-460. 
摘要 ( 774 )   HTML ( 1)   PDF (2047KB) ( 692 )  
相关文章 | 计量指标
提出一种基于超宽带(ultra wideband, UWB)信号到达时间估计(time of arrival,TOA)/到达角度估计(angle of arrival,AOA)联合估计的无线传感器网络(wireless sensor networks, WSNs)定位方案,只需要一个参考节点就可以实现对其他传感器节点的2D相对定位,并且不需要时钟同步,适合于传感器网络节点的低成本设计需求.利用往返时间(round trip time, RTT)进行TOA估计,给出了基于多径检测的TOA估计算法;利用到达时间差估计(time difference of arrival, TDOA)进行AOA估计,因而无需借助复杂的天线波束赋形技术.同时,分析了定位误差模型对定位性能的影响,并通过IEEE 802.15.4a信道下的仿真实验进行了验证,结果表明了所提方案的有效性.
一种最大化Ad Hoc网络生存期的拓扑控制算法
李晓鸿 王文艳 王 东
2013, 50(3):  461-471. 
摘要 ( 498 )   HTML ( 1)   PDF (3030KB) ( 400 )  
相关文章 | 计量指标
如何延长无线自组网生存期是拓扑控制技术研究的重点.根据无线自组网通信的特点,基于目前使用最广泛的网络生存期定义和能耗模型,综合考虑节点的发送和接收功耗,通过分析网络生存期与节点通信距离、电路损耗及节点负载量的关系,得出拓扑控制与网络生存期的关系.在此基础上提出延长网络生存期的分布式拓扑控制算法MLTC.网络中每个节点收集其邻居节点信息,分布式构建具有最长路径生存期特性的局部生成子图,并选取覆盖所有最优相邻节点的最小发射功率为此节点的发射功率.算法在保证网络连通性与无向性的同时,使得节点能用最小功率构建保存了原图最长生存期路径的子图.理论分析和仿真实验结果表明,MLTC算法在不同的发送和接收功耗比下均能有效延长网络的生存期.
基于链路断开概率的自适应信标交换算法
张衡阳 郑 博 陈校平 于 佳
2013, 50(3):  472-480. 
摘要 ( 585 )   HTML ( 0)   PDF (3227KB) ( 730 )  
相关文章 | 计量指标
在移动无线传感器网络中,贪婪地理路由协议采用周期性信标交换算法来构建和维护邻居节点表会导致通信暂盲现象.针对该问题,首先从理论上分析节点移动对网络连通性的影响,对节点间的链路状态进行Markov链建模,分析推导出链路断开概率的计算公式.根据链路断开概率与运动时间的一一对应关系,提出一种基于链路断开概率的自适应信标交换算法,提高邻居节点表的构建与维护的准确性与实时性,为贪婪地理转发策略提供可靠的依据,减缓节点移动带来的不利影响.仿真结果表明,该算法不但提高了数据分组传送成功率,而且还降低了控制开销,适用于对传输可靠性和能耗要求高的移动无线传感器网络.
一种面向网格计算的自适应动态冗余预留策略
肖 鹏, 胡志刚,
2013, 50(3):  481-489. 
摘要 ( 499 )   HTML ( 0)   PDF (2776KB) ( 398 )  
相关文章 | 计量指标
针对网格环境中冗余机制在系统可靠性和任务执行效率之间难以平衡的问题,提出一种冗余度可动态调整的自适应冗余策略.该策略以可靠性指标为约束条件,依据负载变化自适应地优化系统冗余度,在不降低可靠性的前提下减少冗余度过高对网格任务执行效率的负面影响.理论分析给出了冗余度与可靠性之间的量化关系,实验分析对比了该动态冗余策略与其他冗余策略的性能差异,并对策略关键参数进行了对比分析.实验结果显示,当系统面临较高的任务负载或负载变化剧烈时,自适应的动态冗余预留策略能够显著提高资源有效利用率,并在任务执行效率和系统可靠性之间实现动态平衡,从而降低传统冗余策略对系统性能的负面影响.
一种能量有效的双层传感器网络Top-k安全查询机制
廖晓静 李建中 余 磊
2013, 50(3):  490-497. 
摘要 ( 512 )   HTML ( 0)   PDF (1615KB) ( 503 )  
相关文章 | 计量指标
在双层传感器网络中,高层具有相对较高存储能力和计算能力的存储节点负责收集低层资源受限的传感器节点的感知数据,完成数据存储和回答用户的查询请求.但是由于传感器网络经常部署在不安全环境下,存储节点可能被俘获从而向用户返回错误的查询结果,因此查询结果的正确性验证至关重要.针对双层传感器网络下时隙top-k查询,提出了一种能量有效的top-k安全查询机制RSTOPK,用以验证查询结果的认证性和完全性.通过结合计算承诺的假设检验方法,有效提高了对错误查询结果的检测率,并有效减小了查询结果验证引入的额外通信开销.理论分析和模拟实验结果表明了其有效性.
基于上下文验证的网络入侵检测模型
田志宏 王佰玲 张伟哲 叶建伟 张宏莉
2013, 50(3):  498-508. 
摘要 ( 697 )   HTML ( 1)   PDF (2360KB) ( 637 )  
相关文章 | 计量指标
大量误报引发的可信问题一直是入侵检测研究领域所面对的具有挑战性的未解技术难题之一.为了提高入侵检测系统的确定性和准确性,必须对其告警信息加以区分,滤除无效攻击导致的虚警,从而自动准确地识别有效攻击.由此,提出了一种基于上下文验证的网络入侵检测模型,结合环境上下文、弱点上下文、反馈上下文和异常上下文等多种上下文信息,构建了一个以上下文为中心、多种验证技术相结合的高效、稳定、完整、易管理、可扩充的虚警处理平台,实现了告警的自动验证以及攻击行为能否成功地自动判定,从而达到滤除虚警的目的,使入侵检测系统起到真正的预警作用.
因特网时延空间中TIV与接入时延的研究
王占丰 陈 鸣 邢长友 白华利 魏祥麟
2013, 50(3):  509-516. 
摘要 ( 470 )   HTML ( 0)   PDF (1161KB) ( 474 )  
相关文章 | 计量指标
大量网络测量研究证实了违反三角不等式(TIV)是因特网时延空间存在的一种普遍现象,是影响网络坐标系统准确性的重要原因之一.通过将因特网分为接入网和核心网两部分,引入了时延空间模型来分析接入时延对于TIV的影响.理论分析表明TIV产生于网络的核心,接入时延可以使得在端到端路径中观察到的TIV数目会减少,并减轻TIV的严重程度.然后,在PlanetLab测试平台设计了一组网络测量实验,来测量端到端的时延矩阵和相应的拓扑信息.之后,设计了ScoutTIV算法来统计时延数据集中的TIV比例.在实验中,根据主机的IP属性将其分为3个子集,并生成了1个随机数据集来进行分析.在所有子集上的实验结果与理论分析结论一致,为网络坐标系统进一步提高预测精度提供了重要依据.
中心计算的无线传感器网络2-不相交路径路由算法
于磊磊, 陈冬岩, 刘月美, 黄 旭,
2013, 50(3):  517-523. 
摘要 ( 575 )   HTML ( 0)   PDF (1864KB) ( 549 )  
相关文章 | 计量指标
在多路径路由(multipath routing, MPR)算法中,不相交多路径路由(disjoint multipath routing, DMPR)算法具有更高的可靠性和容错性.DMPR算法面临的主要挑战有2点:不相交路径的选优问题和数据包在不相交路径上的传输问题.针对某些工业应用(例如矿井环境监测)中网络拓扑比较稳定,sink节点运算和存储能力较强等特点,提出了一种中心计算的2-不相交路径路由算法——CCDMPR算法.算法利用全网信息计算出从源节点到sink节点的近似最优2-节点(链路)不相交路径,然后生成仅包含主父交节点,辅父节点对和路径比特序列的微路由表并下传到每个节点;针对中心计算方式对链路状态变化的反应迟缓问题,采用了一种中心调度的自适应机制提高路径维护的灵活性.实验结果证明,CCDMPR算法能够显著减小平均路径长度,节省网络整体能量,并能提高数据传输的可靠性.
一种抗多径和阴影的视距指纹定位算法
陈永乐, 朱红松, 孙利民,
2013, 50(3):  524-531. 
摘要 ( 400 )   HTML ( 0)   PDF (2748KB) ( 471 )  
相关文章 | 计量指标
针对指纹定位算法在实际应用中普遍面临的由人身遮挡造成的多径和阴影干扰问题,通过实验深入分析人身遮挡对指纹算法中信号强度变化的影响,发现利用视距指纹代替原始指纹可以彻底避免阴影的出现,同时也能有效减少多径的影响,在此基础上提出了一种双定位节点的视距指纹定位算法(LoSF).针对视距指纹中存在的异常,LoSF算法还设计了相应的误差处理算法排除视距指纹中的误差数据.通过与现有算法的比较,LoSF算法性能达到了中位数误差2m的精确度,远高于基于原始指纹的RADAR算法所得到的6m精度,也要比带有朝向指纹的COMPASS算法获得的4.2m精度提高一倍之多.
一种新的基于指纹的密钥隐藏方案
李西明, 杨 波, 郭玉彬, 姚金涛,
2013, 50(3):  532-539. 
摘要 ( 614 )   HTML ( 0)   PDF (2299KB) ( 411 )  
相关文章 | 计量指标
针对已有指纹密钥隐藏方法的不足,提出了一种新的基于指纹的密钥隐藏方案,为了充分利用指纹图像细节点以及细节点周围的纹理信息,采用了一种新定义的指纹模板:细节点纹理串模板,这种密钥隐藏方案也就称为细节点纹理串密钥隐藏方案.在此方案中,首先提取指纹的细节点集合,然后在每个细节点周围使用Gabor滤波器滤波,以提取细节点周围的指纹纹理信息,细节点集合和每个细节点对应的纹理信息共同构成细节点纹理串模板.然后,用(n,k)秘密分割方法将对称加密系统或PKI产生的密钥分成n份秘密值,每份秘密值以保密的方式存储在细节点对应的纹理串中,只有当询问指纹能恢复出至少k份秘密时,才可以恢复出原密钥.在指纹数据库FVC2002 DB1和DB2上的实验表明,一指纹用于隐藏密钥,另一指纹用于恢复密钥的情况下,该方案的等错率(equal error rate, EER)为1%~2.2%,优于模糊盖子密钥隐藏方案.安全性分析表明,该方案有效地保护了密钥以及指纹模板信息,安全度高于模糊盖子方案.
一种适用于卫星通信网络的端到端认证协议
张小亮, 涂勇策, 马恒太, 杨治安, 胡晓惠,
2013, 50(3):  540-547. 
摘要 ( 523 )   HTML ( 3)   PDF (3204KB) ( 480 )  
相关文章 | 计量指标
随着卫星通信网络组网技术的发展,卫星通信网络安全防护技术日益受到人们的关注,端到端认证是其中一项关键技术.针对目前认证协议效率过低,认证时间过长的问题,在建立卫星通信网络安全认证模型的基础上,设计了新的端到端认证协议并构建了安全认证仿真系统,以语音和视频业务为例对协议进行了仿真验证.仿真的结果表明安全认证用时远远小于传输用时,充分体现了该认证协议的高效性.
一种基于隶属度优化的演化聚类算法
侯 薇, 董红斌, 印桂生,
2013, 50(3):  548-558. 
摘要 ( 539 )   HTML ( 0)   PDF (1917KB) ( 513 )  
相关文章 | 计量指标
针对FCM中数据点隶属度的计算是影响算法执行效率的主要因素,提出一种新的加速FCM算法(accelerated fuzzy C-means, AFCM),用于加速FCM及基于FCM的演化聚类算法.AFCM算法采用抽样初始化操作,产生较好的初始聚类中心,对于拥有较大隶属度的数据点,通过一步k-means操作更新模糊聚类中心,同时仅更新小隶属度来达到加速FCM算法的目的.为了验证所提出方法的有效性并提高聚类算法的效率,将AFCM应用于基于演化算法的模糊聚类算法.实验表明,此方法在保持良好的聚类结果前提下,能够减少大规模数据集上聚类算法的计算时间.
基于证据理论的本体不一致性度量方法研究
李冬梅, 林友芳, 黄厚宽, 田 萱,
2013, 50(3):  559-567. 
摘要 ( 554 )   HTML ( 0)   PDF (849KB) ( 536 )  
相关文章 | 计量指标
随着语义网技术的发展,本体不一致性问题成为本体研究中的热点之一.度量本体的不一致度是处理本体不一致的基础和前提.在分析证据理论不确定推理方法特点与本体不一致性度量问题特点的基础上,提出了一种基于证据理论的本体不一致性度量ETOICM方法,对相关结果进行了证明,给出了度量的计算公式和实现算法,通过实验将该方法与相关方法进行对比分析,说明了该方法的特点.另外,ETOICM方法的度量结果可以作为权重值,为下一步采用不确定性方法进行本体不一致的诊断修复和推理工作提供依据.
一种基于Wi-Fi 信号指纹的楼宇内定位算法
牛建伟 刘 洋 卢邦辉 宋文芳
2013, 50(3):  568-577. 
摘要 ( 674 )   HTML ( 1)   PDF (3123KB) ( 445 )  
相关文章 | 计量指标
由于GPS无法在楼宇内使用,而目前的楼宇内定位技术一般都需要预先部署额外的设施,因此楼宇内无基础设施定位成为了一个热点研究问题.提出了一种利用Wi-Fi接入点的MAC地址和RSSI(received signal strength indication)值,通过机器分类的方式实现楼宇内房间级定位的算法R-kNN(relativity k-nearest neighbor).R-kNN是一种属性加权k近邻算法,它通过将AP之间的相关性反应在权值的分配上,有效地降低了维度冗余对分类准确率的负面影响.R-kNN没有对房间和AP的物理位置做出任何假设,只需要使用环境中现存的AP就可以取得较好的定位效果,无需部署任何额外设施或修改现有设施.实验结果表明,在AP数量较多的楼宇环境中,R-kNN能够取得比k近邻算法和朴素贝叶斯分类器更好的定位效果.
基于聚类杂交的隐私保护轨迹数据发布算法
吴英杰, 唐庆明, 倪巍伟, 孙志挥, 廖尚斌,
2013, 50(3):  578-593. 
摘要 ( 589 )   HTML ( 0)   PDF (5694KB) ( 580 )  
相关文章 | 计量指标
传统关于轨迹数据发布的隐私保护研究大多采用聚类技术,其相关算法只关注每条轨迹的隐私保护,忽视对轨迹聚类组特征的保护.通过理论分析和实验验证发现,对采用聚类发布技术产生的轨迹数据进行二次聚类,可得到原始轨迹数据在发布之前的聚类组特征,从而可能导致隐私泄露.为了有效预防二次聚类攻击,提出一种(k,δ,Δ)-匿名模型和基于该模型的聚类杂交隐私保护轨迹数据发布算法CH-TDP,算法CH-TDP对采用(k,δ)-匿名模型及相关算法处理得到的聚类分组先进行组间杂交,而后再进行组内扰乱,其目标在防止出现二次聚类攻击的前提下,保证发布轨迹数据的质量不低于阈值Δ.实验对算法CH-TDP的可行性及有效性与同类算法进行比较分析,结果表明算法CH-TDP是有效可行的.
适用于范围查询的列存储数据桶划分算法
李晔锋 乐嘉锦 王 梅
2013, 50(3):  594-601. 
摘要 ( 1230 )   HTML ( 0)   PDF (1243KB) ( 581 )  
相关文章 | 计量指标
范围查询是数据库中一项重要的操作.列存储数据库中,能否有效查找一个范围内的属性值,获取对应的行号集合,将极大影响元组重构的效率.与树型结构相比,Hash表对数据的精确查找具有更高的效率,但是范围查找的效率比较低.针对这种情况,提出了一种改进的可用于范围查询的数据桶划分算法.为了能够更好地对算法进行描述,首先提出了可用于范围查询的Hash存储模型(ranged Hash, RH),并给出了桶的值域和序列化的定义.其次针对列存储等“读优先”特性,在RH模型的基础上,提出一种改进的桶划分算法.该算法生成可序列化的哈希函数把属性值划分到桶中,能够同时提高属性值的范围查询效率和存储效率.最后,通过实验结果验证算法的有效性.
一种带参数的Hylomorphisms及其计算律
余珊珊, 李师贤, 苏锦钿,
2013, 50(3):  602-618. 
摘要 ( 436 )   HTML ( 0)   PDF (2364KB) ( 378 )  
相关文章 | 计量指标
针对函数式程序语言中的一般hylomorphisms无法描述带参数的递归计算的问题,利用完全偏序范畴上的多项式函子分别给出带固定参数和累积参数的hylomorphisms——phylo射和ahylo射,证明了它们在固定参数和累积参数下都是唯一的,从而将Pardo对带参数的递归计算pfold和afold的研究扩展到hylomorphisms中,使得在hylomorphisms中可以直接包含额外的参数用于作为计算的输入或者保存临时的累积计算结果;从范畴论的角度分析了phylo射和ahylo射与其他各种递归及共递归之间的关系及其计算律,并利用函数程序语言Haskell给出相应的实现.
神经网络在软件多故障定位中的应用研究
何加浪, 张 宏,
2013, 50(3):  619-625. 
摘要 ( 536 )   HTML ( 0)   PDF (1593KB) ( 519 )  
相关文章 | 计量指标
针对软件多故障定位问题,提出一种基于神经网络的多故障定位模型.通过故障相关性分析,计算故障定位使用的输入对每个故障的支持度分量.利用神经网络模型学习输入的覆盖位置与各故障间的关系,针对每个可能包含故障的位置,构建理想输入作为已学习神经网络的输入,计算出该位置包含各故障的支持度,最终对每个故障确定其按支持度排序的位置序列,从而完成多故障定位的任务.实验结果表明,较传统方法,该模型对各故障可疑位置具有很强的分辨能力,表现出较大的优越性,对于提高软件多故障调试效率有很大帮助.
软件动态正确性的形式化描述
马艳芳, 张 敏, 陈仪香,
2013, 50(3):  626-635. 
摘要 ( 363 )   HTML ( 0)   PDF (1046KB) ( 450 )  
相关文章 | 计量指标
软件正确性是一个逐渐改进的过程.通过不断地修改,软件越来越接近于正确.同时软件的执行依赖于环境.为了刻画软件的动态正确性并考虑环境的因素,以参数化互模拟为基础,利用极限的观点,建立软件动态正确性的形式化描述.首先建立参数化互模拟的无限演化理论,给出参数化极限互模拟的定义,并给出几个特殊的参数化极限互模拟实例.其次,建立参数化互模拟极限,给出参数化互模拟极限的规约刻画. 最后,证明参数化互模拟极限的唯一性、与参数化互模拟的相容性等代数性质.
云计算环境下适于工作流的数据布局方法
张 鹏, 王桂玲, 徐学辉,
2013, 50(3):  636-647. 
摘要 ( 464 )   HTML ( 0)   PDF (3238KB) ( 981 )  
相关文章 | 计量指标
云计算环境下的工作流管理系统,适合支持需要高效的计算性能和大规模存储的跨组织业务协作,在应急管理、供应链管理和健康医疗等领域具有广泛的应用前景.然而,在大量并发工作流实例的情况下,当工作流的任务需要不同位置的数据,特别是涉及客户端隐私数据时,如何有效地存放这些数据、优化数据传输就成为其中的挑战.为此,云计算环境下适于工作流的数据布局方法能够根据数据的隐私要求把数据存放到云端和客户端,并且在工作流运行时根据控制流动态地调整数据布局,减少数据传输.实验表明,该方法能够有效减少工作流运行时的数据传输.
对角线稀疏矩阵的SpMV自适应性能优化
孙相征, 张云泉, 王 婷, 李 焱, 袁 良,
2013, 50(3):  648-656. 
摘要 ( 785 )   HTML ( 2)   PDF (1905KB) ( 546 )  
相关文章 | 计量指标
稀疏矩阵向量乘(SpMV)是科学计算中常用的内核之一,其运行速率跟非零元分布相关.针对对角线稀疏矩阵,提出了压缩行片段对角(compressed row segment diagonal, CRSD)存储格式.它利用“对角线格式”有效描述矩阵的对角线分布,区别于以往通用的计算方法,CRSD通过对给定应用的对角线稀疏矩阵采样再进行特定的优化.并且在软件安装阶段,通过自适应的方法选取适合具体运行平台的最优SpMV实现.在CPU端进行多线程并行化实现时,自适应调优过程中收集的信息还被用于线程间任务划分,以实现负载平衡.同时完成CRSD存储格式在GPU端的实现,并根据GPU端计算与访存的特点进行优化.实验结果表明:在Intel和AMD的多核平台使用相同线程数的情况下,与DIA相比,使用CRSD的加速比可以达到2.37X(平均1.7X);与CSR相比,可以达到4.6X(平均2.1X).
曲面上旅行商问题的多项式时间近似方案
王 刚 骆志刚
2013, 50(3):  657-665. 
摘要 ( 787 )   HTML ( 0)   PDF (1388KB) ( 477 )  
相关文章 | 计量指标
欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.
基于自组装模型的最大团问题DNA计算算法
李肯立 罗 兴 吴 帆 周 旭 黄 鑫
2013, 50(3):  666-675. 
摘要 ( 581 )   HTML ( 1)   PDF (3502KB) ( 473 )  
相关文章 | 计量指标
DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势. 但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点. 如何提高DNA计算结果的准确性在DNA计算研究中日显重要. 针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法. 算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法. 算法设计的tiles种类为Θ(n+|E|),生化操作复杂性为Θ(1),其中n为图的顶点数,|E|为边数. 与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.