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

当期目录

2016年 第53卷 第11期    出版日期:2016-11-01
信息安全
Android应用第三方推送服务安全分析与安全增强
路晔绵,李轶夫,应凌云,谷雅聪,苏璞睿,冯登国
2016, 53(11):  2431-2445.  doi:10.7544/issn1000-1239.2016.20150528
摘要 ( 1029 )   HTML ( 1)   PDF (2832KB) ( 631 )  
相关文章 | 计量指标
推送服务已成为移动智能终端应用的一个基础服务,各大手机平台及互联网公司相继推出了各自的推送服务供应用程序开发者使用.为了降低资源消耗,部分第三方Android推送服务采用共享通道的设计方式,在设备上使用某个应用的推送后台组件作为其他应用推送数据的分发中心.由于缺乏针对数据机密性、完整性、不可伪造性等安全需求的设计与实现,数据分发环节面临多种攻击的威胁.分析了使用共享通道的第三方Android推送服务在数据分发环节存在的安全问题,通过在攻击程序中Hook相关API调用的方法,实现了针对其他应用推送数据的窃听、篡改、伪造和重放攻击,实验结果表明:大部分共享通道的第三方Android推送服务无法抵抗这些攻击,可能造成用户隐私数据泄露和钓鱼攻击等实际危害.在上述研究的基础上,设计并实现了Android应用推送服务安全增强方案SecPush,使用加密算法及HMAC运算提供推送数据分发环节的安全保护,实验结果表明:SecPush提高了推送数据的安全性,可有效抵挡窃听、篡改、伪造和重放等攻击行为.
多服务器架构下认证与密钥协商协议
万涛,刘遵雄,马建峰
2016, 53(11):  2446-2453.  doi:10.7544/issn1000-1239.2016.20150107
摘要 ( 757 )   HTML ( 2)   PDF (876KB) ( 676 )  
相关文章 | 计量指标
随着网络应用的广泛发展,网络中服务器的体系结构通常由许多不同的服务器组成.多服务器架构下的认证与密钥协商协议是实现远程用户认证的关键.单次注册是多服务架构下的认证与密钥协商协议的最重要特性,而采用动态的身份进行登录认证能有效地保护隐私.Chuang等人结合智能卡和生物特征,提出了一种基于可信计算的匿名可认证密钥协商协议,并指出其协议适用于多服务器环境同时能满足其必需的安全需求.分析指出Chuang等人的协议并不能实现用户的匿名性,同时还容易遭到服务器假冒攻击和智能卡丢失攻击.为了弥补这些安全缺陷,设计每个应用服务器选用不同的秘密参数,提出了一种改进方案.通过对敌手可能的攻击行为分析,证明了改进方案能有效防范服务器假冒攻击、智能卡丢失攻击、窃听攻击、重放攻击等安全威胁,同时改进协议保持着运算简单的特性.
一种基于分块混淆的动态数据隐私保护机制
张宏磊,史玉良,张世栋,周中民,崔立真
2016, 53(11):  2454-2464.  doi:10.7544/issn1000-1239.2016.20150553
摘要 ( 711 )   HTML ( 1)   PDF (2687KB) ( 541 )  
相关文章 | 计量指标
云计算环境下,基于分块混淆的隐私保护机制通过对租户个性化隐私保护需求及应用性能的有效结合,实现了隐私信息在明文状态下的保护.然而随着云端多租户应用的持续运行,一方面,租户数据的插入、删除和修改等业务操作将会影响底层数据存储的分布状态,使分块间的关联关系因数据分布的不均匀而面临极大的泄露风险;另一方面,攻击者仍然可以通过局部时间内各分块的操作日志以及对应的数据快照分析出部分隐私信息.针对上述挑战,在三方安全交互模型的基础上,提出一种面向分块混淆的动态数据隐私保护机制.该机制通过可信第三方对新插入和修改的数据进行缓存并在满足条件时将数据进行分组和存储;通过保留关键分片来保证删除操作中被删数据和剩余数据的隐私安全;通过伪造数据回收机制实现存储资源消耗的降低和应用性能的优化.通过实验证明,提出的动态数据隐私保护机制具有较好的可行性和实用性.
基于白盒密码的DCAS终端安全芯片方案
许涛,武传坤,张卫明
2016, 53(11):  2465-2474.  doi:10.7544/issn1000-1239.2016.20150546
摘要 ( 688 )   HTML ( 1)   PDF (3114KB) ( 382 )  
相关文章 | 计量指标
在国家广电总局2012年发布的可下载条件接收系统(downloadable conditional access system, DCAS)技术规范中,终端的密码操作都被置于安全芯片内,用安全硬件技术加以保护.然而安全芯片中过多的黑盒内容降低了芯片的通用性,增加了研发成本.因此提出一种基于白盒密码的DCAS安全芯片改进方案,利用芯片外的白盒解密软件模块和芯片内的外部编码,替换原方案中的层级密钥模块,并给出了一种在安全芯片内根据参数生成外部编码的算法,重新设计了DCAS终端的解密和握手验证过程.改进后的方案不但弥补了技术规范中原方案的缺点,还增加了如下优点:解密算法与业务密钥都包含在白盒密码模块内,可以同时通过网络下载更新;握手验证过程不仅对DCAS终端设备进行可用性验证,还能够进行唯一性验证.
一个高效可完全模拟的n取1茫然传输协议
魏晓超,蒋瀚,赵川
2016, 53(11):  2475-2481.  doi:10.7544/issn1000-1239.2016.20150505
摘要 ( 1105 )   HTML ( 4)   PDF (837KB) ( 464 )  
相关文章 | 计量指标
茫然传输(oblivious transfer, OT)是一个重要的密码学基础工具,可以被应用到许多密码学协议的构造中去,例如安全多方计算、隐私信息检索等.在n取1茫然传输场景中有2个参与方,即发送方S和接收方R.发送方有n个输入值,接收方希望得到其中某一个值.与此同时协议要保证发送方不知道接收方的选择信息,且接收方除了得到自己选择的值以外不知道其他输入值的相关信息.已有的OT\+1\-n协议仅能保证参与方的输入隐私性或实现单边模拟,均不能实现完全模拟.完全模拟意味着在理想/现实模拟范例中,当接收方或发送方被分别腐化时,协议都可以被模拟,较之于只保证隐私性和单边模拟,其安全性更强.首次在标准恶意敌手模型下,基于判定Diffie-Hellamn (decisional Diffie-Hellamn, DDH)困难问题假设构造了一个高效、可完全模拟的OT\+1\-n协议,该协议的思想主要基于双模式加密机制,并结合知识的零知识证明系统.协议具有常数轮交互复杂度,且计算和通信复杂度仅与n线性相关.
基于RLWE的身份基认证密钥交换协议
赵秀凤,高海英,王爱兰
2016, 53(11):  2482-2490.  doi:10.7544/issn1000-1239.2016.20150547
摘要 ( 1040 )   HTML ( 3)   PDF (910KB) ( 498 )  
相关文章 | 计量指标
提出了一个基于分圆环上错误学习(learning with errors, LWE)问题的身份基认证密钥交换协议,其基本思想是利用环上错误学习(ring learning with errors, RLWE)采样生成系统主私钥,进一步生成用户私钥,通过交换Diffie-Hellman临时公钥,计算用于派生会话密钥的密钥材料. 该协议与传统密钥交换协议的区别在于,协议中引入了错误项,以理想格的解码基为工具,详细分析协议的容错性,给出了合理的参数设置建议,从而保证协议以显著概率计算出相同的会话密钥. 协议在ID-BJM模型下具有可证明AKE安全性和PKG安全性,并且在双方临时私钥泄露、双方长期私钥泄露以及A的长期私钥和B的临时私钥泄露这3种情况下也可以保证协议的AKE安全.
基于声誉机制的网络编码抗污染攻击方案
王铁峰,蔡英,张玉洁
2016, 53(11):  2491-2499.  doi:10.7544/issn1000-1239.2016.20150502
摘要 ( 634 )   HTML ( 0)   PDF (1620KB) ( 566 )  
相关文章 | 计量指标
网络编码在提高网络吞吐量方面有很大的优势,但是它极易受到污染攻击.目前针对此问题的多数解决方案都是针对有中心机制的网络.针对无中心机制的移动自组织网络,考虑移动自组网中节点的移动性和无固定的可信任第三方中心机制,结合已有的声誉机制研究,提出一种基于声誉机制的抗污染攻击方案对抗网络编码中的污染攻击.该方案采用对污染攻击进行检测和定位,在检测污染攻击存在的情况下,通过声誉机制对恶意节点进行定位,从而达到抗污染攻击的目的.通过实验仿真,与已有的方案进行比较,实验结果表明:针对无中心机制的方案在包的接收成功率上有一定提高,并且在多个恶意节点存在的情况下依然可以准确定位出恶意节点并将其隔离.
基于MapReduce的OpenFlow网络属性验证技术
刘艺,雷程,张红旗,杨英杰
2016, 53(11):  2500-2511.  doi:10.7544/issn1000-1239.2016.20150521
摘要 ( 661 )   HTML ( 0)   PDF (2577KB) ( 565 )  
相关文章 | 计量指标
针对OpenFlow网络中由程序自动改变数据平面状态方式引起的流表配置错误问题,提出1种基于MapReduce的OpenFlow网络属性验证技术.首先,利用OpenFlow网络控制转发分离的特点,设计支持实时与非实时2种验证方式的技术架构.其次,提出基于MapReduce模型的非实时验证算法,在Map阶段划分规则等价类,在Reduce阶段构建基于交换机端口谓词的网络转发图并分析可达性,以实现对网络属性的并行验证.与此同时,利用原子谓词消除谓词集合冗余项和规则匹配域转换的方法,提高可达性分析效率.此外,在非实时验证算法的基础上,结合网络更新事件提出实时验证算法,实现网络状态改变时的增量式网络属性验证.最后,理论分析和仿真实验验证了该技术的运行效率和存储开销,并分析了其对TCP连接建立时间的影响.
基于MPTCP的多路径传输优化技术综述
薛开平,陈珂,倪丹,张泓,洪佩琳
2016, 53(11):  2512-2529.  doi:10.7544/issn1000-1239.2016.20150589
摘要 ( 1749 )   HTML ( 15)   PDF (3260KB) ( 854 )  
相关文章 | 计量指标
新型网络环境致力于为用户提供广覆盖、高带宽、包含各种多媒体业务的服务,而多种接入技术并存的网络环境为无处不在的高质量服务提供了可能.为了适应异构环境,用户终端通常配置多个接口(比如WIFI和4G),通信终端之间可能存在多条路径.多径TCP协议(multipath TCP, MPTCP)是IETF MPTCP工作组提出的新型传输层多径协议,它在兼容TCP协议的基础上,同时利用多条路径的传输能力来进行数据传输,提高带宽利用率,增强连接的恢复能力,并且能够自适应地将数据从拥塞路径转移到非拥塞路径.近年来国内外机构先后作出了大量的研究,逐步使得MPTCP由概念走向实用.总结和阐述了MPTCP相关方面的研究现状,其中包括仿真实现与实际部署、乱序控制、联合拥塞控制、能耗管理、安全以及关于路径选择、移动性和QoS、数据中心中的应用等其他方面的研究.最后给出总结和展望.
面向磁盘驻留的类Pregel系统的多级容错处理机制
毕亚辉,姜苏洋,王志刚,冷芳玲,鲍玉斌,于戈,钱岭
2016, 53(11):  2530-2541.  doi:10.7544/issn1000-1239.2016.20150619
摘要 ( 601 )   HTML ( 0)   PDF (3162KB) ( 303 )  
相关文章 | 计量指标
基于BSP模型的分布式框架已经成为大规模图高频迭代处理的有效工具.分布式系统可以通过增加集群节点数量的方式提供弹性的处理能力,但同时也增加了故障发生的概率,因此亟需开发高效的容错处理机制.现有工作主要是基于检查点机制展开研究,包括数据备份和故障恢复2部分:前者没有考虑迭代过程中参与计算的数据规模的动态变化,而是备份所有图数据,因此引入了冗余数据的写开销;后者通常是从远程存储节点上读取备份数据进行故障恢复,而没有考虑利用本地磁盘数据恢复某些场景下的故障,引入额外的网络开销.因此提出了一种多级容错处理机制,将故障分为计算任务故障和计算节点故障2类,并设计了不同的备份和恢复策略. 备份阶段利用了某些应用在迭代计算过程中参与计算的数据规模的动态变化特性,设计了完全备份和写变化log自适应选择的策略,可以显著减少冗余数据的写开销.故障恢复阶段,对任务故障,利用本地磁盘上保留的图数据和远程的消息数据完成恢复;而对节点故障,则利用备份在远程信息进行恢复.最后,通过在真实数据集上的大量实验,验证了提出的多级容错机制的有效性.
人工智能
基于关键词精化和句法树的商品图像句子标注
张红斌,姬东鸿,尹兰,任亚峰,牛正雨
2016, 53(11):  2542-2555.  doi:10.7544/issn1000-1239.2016.20150906
摘要 ( 869 )   HTML ( 0)   PDF (2820KB) ( 421 )  
相关文章 | 计量指标
商品图像句子标注是图像标注中一项既有趣又富有挑战的研究任务.噪声单词干扰和句法结构错误是该项研究的制约因素,针对噪声单词干扰,提出关键词精化思想:用绝对排序特征强化关键词权重,完成第1次关键词精化;计算单词的语义相关度评分,进一步优选能准确刻画图像内容的单词,完成第2次关键词精化.设计词序列"拼积木"算法,把关键词拼装成N元词序列.针对句法结构错误,提出句法树思想:基于N元词序列和句法子树递归地构建一棵完整的句法树,遍历该树叶子结点输出句子,标注商品图像.实验结果表明:关键词精化和句法树均有助于改善标注性能,句中的语义信息兼容性和句法模式兼容性得以保持,句子内容更连贯、流畅.
结合SE-Tree结构特征的极小碰集求解算法
刘思光,欧阳丹彤,王艺源,贾凤雨,张立明
2016, 53(11):  2556-2566.  doi:10.7544/issn1000-1239.2016.20150396
摘要 ( 634 )   HTML ( 2)   PDF (3268KB) ( 332 )  
相关文章 | 计量指标
在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.
组加权约束的核稀疏表示分类算法
郑建炜,杨平,王万良,白琮
2016, 53(11):  2567-2582.  doi:10.7544/issn1000-1239.2016.20150743
摘要 ( 670 )   HTML ( 0)   PDF (4779KB) ( 461 )  
相关文章 | 计量指标
提出了一种称为核加权组稀疏表示分类器(kernel weighted group sparse representation classifier, KWGSC)的新型模式分类算法. 通过在核特征空间而非原输入空间引入组稀疏性和保局性,KWGSC能够获得更有效的鉴别性重构系数用于分类表示. 为获得最优重构系数,提出了一种新的迭代更新策略进行模型求解并给出了相应的收敛性证明以及复杂度分析. 对比现存表示型分类算法,KWGSC具有的优势包括:1)通过隐含映射变换,巧妙地规避了经典线性表示算法所固有的规范化问题;2)通过联合引入距离加权约束和重构冗余约束,精确地推导出查询样本的目标类别标签;3)引入l\-2,p正则项调整协作机制中的稀疏性,获得更佳的分类性能. 人造数值实验表明:经典线性表示型算法在非范数归一化条件下无法找到正确的重构样本,而KWGSC却未受影响. 实际的公共数据库验证了所提分类算法具有鲁棒的鉴别力,其综合性能明显优于现存算法.
DNA自组装计算模型求解二部图完美匹配问题
蓝雯飞,邢志宝,黄俊,强小利
2016, 53(11):  2583-2593.  doi:10.7544/issn1000-1239.2016.20150312
摘要 ( 610 )   HTML ( 1)   PDF (3782KB) ( 528 )  
相关文章 | 计量指标
针对二部图完美匹配问题,提出了一种基于DNA计算自组装模型的算法.首先,通过该算法求解了一个具有10个顶点的二部图完美匹配问题的实例,实例中给出DNA计算自组装模型算法所涉及到的DNA Tile的编码设计方案、自组装计算步骤及结果分析;然后,给出了任意二部图完美匹配问题的求解方案;最后,针对DNA计算自组装模型算法解决任意二部图完美匹配问题的时间和空间消耗进行了讨论.结果表明:对任意二部图只需14种Tile类型就能够得到完美匹配.
分类数据的多目标模糊中心点聚类算法
周治平,朱书伟,张道文
2016, 53(11):  2594-2606.  doi:10.7544/issn1000-1239.2016.20150467
摘要 ( 803 )   HTML ( 0)   PDF (3152KB) ( 458 )  
相关文章 | 计量指标
针对传统面向分类属性数据的聚类算法大多是对单一指标优化而存在的局限性,将类内和类间信息同时引入到优化过程中,结合多目标优化算法与模糊中心点聚类,提出一种新颖的多目标模糊聚类算法.与传统的基于遗传算法的混合聚类方法不同的是,采用模糊隶属度对染色体进行编码,同时优化2个相对的聚类目标函数获得一组最优解集,并且采用了一种提前终止准则判断算法是否达到稳定状态并停止操作,以减少不必要的计算开销.为了进一步提高算法的效率,通过采样子集计算出相应的模糊中心点作为类的表达,然后以这些模糊中心点计算出全体样本的隶属度矩阵即可获得最终的聚类结果.对10种数据集的实验结果表明:所提方法在聚类精度和稳定性方面优于当前最新的多目标聚类算法,且计算效率也获得较大的提升.
信息表中概念漂移与不确定性分析
邓大勇,苗夺谦,黄厚宽
2016, 53(11):  2607-2612.  doi:10.7544/issn1000-1239.2016.20150803
摘要 ( 658 )   HTML ( 2)   PDF (658KB) ( 362 )  
相关文章 | 计量指标
概念漂移探测是数据流挖掘的一个研究重点,不确定性分析是粗糙集理论的研究核心之一. 结合数据流、概念漂移和粗糙集、F-粗糙集的基本观点,以上下近似为工具,定义了上下近似概念漂移、上下近似概念耦合等概念,据此分析了信息表内概念随着属性而变化的特点. 以正区域为工具,定义了决策表内概念漂移、概念耦合等概念,分析了决策表内整体概念随属性变化而变化. 在认识论方面,从理想和现实2方面定义了认识收敛, 从粒计算、粗糙集的角度对人类认识世界的方式进行了探讨.
基于样本权重的不平衡数据欠抽样方法
熊冰妍,王国胤,邓维斌
2016, 53(11):  2613-2622.  doi:10.7544/issn1000-1239.2016.20150593
摘要 ( 1014 )   HTML ( 7)   PDF (1155KB) ( 756 )  
相关文章 | 计量指标
现实世界中广泛存在不平衡数据,其分类问题是数据挖掘和机器学习的一个研究热点.欠抽样是处理不平衡数据集的一种常用方法,其主要思想是选取多数类样本中的一个子集,使数据集的样本分布达到平衡,但其容易忽略多数类中部分有用信息.为此提出了一种基于样本权重的欠抽样方法KAcBag(K-means AdaCost bagging),该方法引入了样本权重来反映样本所处的区域,首先根据各类样本的数量初始化各样本权重,并通过多次聚类对各个样本的权重进行修改,权重小的多数类样本即处于多数类的中心区域;然后按权重大小对多数类样本进行欠抽样,使位于中心区域的样本较容易被抽中,并与所有少数类样本组成bagging成员分类器的训练数据,得到若干个决策树子分类器;最后根据各子分类器的正确率进行加权投票生成预测模型.对19组UCI数据集和某电信运营商客户换机数据进行了测试实验,实验结果表明:KAcBag方法使抽样所得的样本具有较强的代表性,能有效提高少数类的分类性能并缩小问题规模.
基于仿生学的不相关局部保持鉴别分析
宁欣,李卫军,李浩光,刘文杰
2016, 53(11):  2623-2629.  doi:10.7544/issn1000-1239.2016.20150630
摘要 ( 638 )   HTML ( 0)   PDF (1283KB) ( 337 )  
相关文章 | 计量指标
由于形象思维方式是人类的一种本质思维方式,人类通过各种感官来认知事物的规律性,进而提取出具有代表性的特征,因此通过形象思维的方法来提取事物的本质特征符合人类认知事物的规律.针对人脸识别中特征提取问题,该算法以形象认知规律与无监督判别投影为理论基础,提出了一种仿生不相关空间局部保持鉴别分析(biomimetic uncorrelated locality preserving discriminant analysis, BULPDA)算法.算法首先根据人类形象认知的特性构建了一种新的相似系数表示方法;然后结合不相关空间概念,确保矢量空间具有不相关性;最后给出了基于奇异值分解的矢量空间求解方法,形成了一种特征提取新思路.在标准数据库上的实验结果表明,新算法优于传统的特征提取方法和其他改进的局部保持投影方法.
信息处理
一种社会网络用户身份特征识别方法
胡开先,梁英,许洪波,毕晓迪,左遥
2016, 53(11):  2630-2644.  doi:10.7544/issn1000-1239.2016.20150219
摘要 ( 992 )   HTML ( 3)   PDF (5372KB) ( 545 )  
相关文章 | 计量指标
社会网络是现代信息社会重要的组成部分.社会网络用户身份不透明、不可见的特性带来一系列社会安全问题.提出了一种社会网络身份特征识别方法,分别利用基于位置的社会网络和社交关系进行社会网络用户的身份特征识别,融合2种识别结果推测社会网络用户真实身份.提出了一种基于位置的社会网络用户身份识别方法,通过计算中文分词和二元组分词的基本匹配权重和完全匹配权重得到近似度权重,并用它衡量实体为用户所属实体的可能性;通过实体名称聚合算法,对近似度权重计算结果进行优化.根据好友之间倾向于拥有相似的身份特征和相同的兴趣爱好的观察,提出了一种基于社交关系的多数投票的身份识别方法,对社交关系中的用户身份特征进行统计,推测当前用户的地址信息、实体信息和用户兴趣.基于微博数据,进行了样本数为1 000名用户和10 000名用户的2组实验,涵盖了超过250万条社交关系.实验结果表明,提出的虚实映射方法有很高的准确率和覆盖率,与现有方法相比,该方法着眼于推测个人用户细粒度的身份特征,具有较高的实际应用价值.
离线瞬态社会网络中的多用户位置邻近预测
廖国琼,王汀利,邓琨,万常选
2016, 53(11):  2645-2653.  doi:10.7544/issn1000-1239.2016.20150388
摘要 ( 563 )   HTML ( 0)   PDF (2307KB) ( 482 )  
相关文章 | 计量指标
离线瞬态社会网络(offline ephemeral social network, OffESN)是一种在特定时间通过参加特定事件临时组建的新型社会网络.随着移动智能终端的普及和短距离通信技术(如蓝牙、RFID技术等)的发展,该类型网络得到工业界和学术界越来越多的关注.位置邻近(location proximity)关系是指用户在离线网络中的相遇关系.针对位置邻近关系的动态变化性及持续时间短等特征,主要研究离线瞬态社会网络中多用户邻近关系预测问题.首先,给出离线瞬态社会网络中的相关概念及问题定义;然后,设计多用户邻近关系预测总体框架,包括网络片段收集、叠加网络构建、网络过滤及极大紧密子图发现等步骤.由于多邻近关系的数量及每个邻近关系中用户的数量不能事先确定,基于分裂思想提出了一种极大紧密子图挖掘策略,以预测多用户位置邻近关系.该挖掘算法是以加权边介数为网络分裂依据,以聚集密度为分裂结束条件.在2个真实数据集上完成了实验,验证了所提出预测策略的可行性及效率.
基于偏序任务的社会网络合作算法研究
刘勇,韩雪,李金宝,任倩倩,王楠
2016, 53(11):  2654-2665.  doi:10.7544/issn1000-1239.2016.20150617
摘要 ( 557 )   HTML ( 2)   PDF (2898KB) ( 466 )  
相关文章 | 计量指标
针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations, CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集,使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题,然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不仅输出有效的团队,而且能给出团队成员的具体任务分配以及每项任务的开始时间. 真实数据上的实验结果表明: HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.