Online Task Allocation of Spatial Crowdsourcing Based on Dynamic Utility
-
摘要: 为提升众包任务在线分配的总体效用，该文提出一种适用于时空众包环境的在线任务分配方法。该方法针对时空众包环境下的在线任务分配问题，首先提出一种以众包任务为中心的K最近邻算法来进行候选众包工人的选择，进而设计一种基于动态效用的阈值选择算法，实现众包工人与任务的最优分配。实验结果显示，文中所提出算法具有较好的有效性和可行性，并能在一定程度上保证众包工人的可靠性，优化平台总效益。Abstract: In order to improve the overall effectiveness of the online assignment of crowdsourcing tasks, an online task assignment method is proposed for the space-time crowdsourcing environment. To deal with the problem of online task assignment in spatiotemporal crowdsourcing environment, a K-NearestNeighbor (KNN) algorithm is firstly proposed based on crowdsourcing task to select the candidate crowdsourcing workers. Then a threshold selection algorithm based on dynamic utility is designed to realize the optimal allocation of crowdsourcing workers and tasks. Experimental results show that the proposed algorithm is effective and feasible, and can guarantee the reliability of crowdsourcing workers and optimize the overall efficiency of the platform.
-
1. 引 言
电子信息类产品广泛存在于人类点点滴滴的生活中，成为人们生活中不可或缺的组成部分[1]。集成电路作为电子信息类产品的基本单元，随着其向小体积、高密度、高开关速度等方向的快速发展，其在电子信息类产品的组成中发挥着越来越重要的作用，同时带来的电磁兼容性问题也越来越突出。其中，静电放电对电子产品的危害是很大的，它能在瞬间达到几千伏，对集成电路来说有时候是毁灭性的。因此，集成电路静电放电防护研究越来越备受关注[2,3]。
静电放电是指带电体周围的场强超过周围介质的绝缘击穿场强时，因介质电离而使带电体上的静电荷部分或全部消失的现象。静电放电过程往往会产生瞬时脉冲大电流，其强度可达到几十安培甚至上百安培，属于瞬态干扰类型。集成电路静电放电研究由来已久[4,5]，目前在测试、建模等方面均已形成了很多标准[6,7]。同时，在建模、测试、防护等方面的研究[3-5,8,9]层出不穷，不断推进集成电路静电放电防护工作的进展。根据静电放电产生的方式、上升时间、衰减时间以及峰值电流等因素，将其主要划分为几种放电模式：人体模型、机器模型、人体金属模型、组件充电模型、家具模型等，以上模型能够确定失效等级。
另外，随着集成电路工艺水平的不断提升，集成度、小型化、高速度以及应用场景的电磁环境复杂性逐渐提升，集成电路更易受到静电放电干扰的影响，从而使得研究者也不断面临新的挑战。
但是研究静电放电还需要细节，传输线脉冲(Transmission Line Pulse, TLP)测试模型和技术因其可靠、可重复、过程参数能够被观察和记录等特点，被器件级静电放电特性研究广泛采用。TLP是研究静电放电防护公认的有效手段[7,10]。随着TLP测试技术的不断提升，应用TLP解决静电放电问题的研究[11,12]不断涌现。其中，研究者在证明静电放电测试方法和传输线脉冲测试方法结果之间的等效性或相关性方面有较多研究[13-15]。应用TLP技术在集成电路静电放电防护方面也有不少感兴趣的研究者[2]。基于传输线脉冲测试的各种仿真模型也已经被提出并不断改进。其中，分段线性模型由Ralph Santoro[16] 于1995年首次提出，并由Austermann等人[17]作为4种仿真模型之一进行了更为详细的介绍，但是他们所描述的分段线性模型不够完善，有一定的改进空间。
瞬态电压抑制(Transient Voltage Suppression, TVS)二极管是集成电路在进行静电放电防护时，最常采用的防护器件之一。TVS二极管作为防护器件使用时，通常采用两个方式应用到集成电路：一是片外防护，也就是将TVS二极管应用到芯片引脚回路远端；二是片内防护，也就是将TVS二极管直接集成在芯片内部。经过研究者的不断努力，TVS二极管在性能的设计和提高方面不断进步[18,19]。并且，更多的研究致力于应用TVS二极管进行集成电路片上或者片外的防护工作上，如芯片应对瞬态干扰的防护器件建模仿真[20,21]以及防护效果研究[22-25]等。
黄薇等人[20]对该器件在高电压大电流下的反向工作特性建模，在Matlab中利用所建模型仿真，来预测TVS二极管瞬态电压抑制时的电特性。周月宾等人[21]通过PSCAD/EMTDC自身提供的二极管，复合等值模型，有效解决了换流器闭锁、解锁行为的精确模拟问题。张杨等人[26]提出了TVS冲击电压模型，研究了抑制冲击电压措施，有效解决了TVS本身的寄生参数对ESD防护特性的影响。现有研究多为针对防护器件本身的建模仿真和性能提高的研究。Maghlakelidze等人[24]使用TLP测试手段研究了瞬态电压抑制器件对集成电路的防护效果。Zeng等人[25]证明了使用基于瞬态电压抑制器(TVS)二极管的电路在高功率微波(HPM)脉冲下的保护效果。同样是通过测试手段实现防护效果研究。陈强等人[27]依据IEC61000-4-2 ESD应力作用下完成了一款开关芯片防护电路的仿真。由此可见，当前在芯片防护效果研究方面，大多使用实测手段对防护效果开展验证，目前尚未发现应用仿真方法实现基于TLP的集成电路防护研究以及相关的仿真模型。
综上所述，国内外针对瞬态干扰的测试多以ESD等级测试为主，来判断器件是否能承受该级别的干扰，各等级之间的差异很大，缺乏对器件损毁的精确判据。而且，当前针对防护器件的选型和使用主要根据数据手册和工程经验，缺乏对基于器件实测数据的精准把握和精确的防护方法，容易出现过保护或欠保护现象。
因此，本文通过芯片在TLP应力作用下的伏安特性数据，构建了基于实测TLP数据的瞬态干扰模型，并建立了TVS防护器件的等效电路模型，提出了芯片的协同防护设计方法。本文精确地获取了器件的损毁阈值，实现了基于实测数据的精确协同防护设计。
2. 基于TLP测试的芯片分段线性建模方法
基于TLP测试芯片的分段线性建模是以对芯片的TLP测试获得的I-V数据为基础，对其进行近似线性分段后，进行模型的建立。根据分段线性建模方法，近似线性的线段一方面可以通过观察其线性程度，另一方面也可以通过观察I-V曲线的数据判断其线性程度来进行近似线性线段的选取。选取的每一个线段都需要具备近似线性的特点，从仿真成本的角度考虑近似线性线段的数量越少成本越低，但是从仿真精度的角度考虑近似线性线段的数量越多精度越高，因此结合自身对成本和精度的要求来选择合适的近似线性线段来进行仿真。
2.1 芯片的传输线脉冲测试
本文利用TLP自动测试系统，对型号为CD4001BE的芯片上的“B-Vss”回路也就是“输入到地”回路进行了TLP应力下的测试，获得了瞬态电压、瞬态电流、直流下的漏电流等数据。测试中所使用的传输线脉冲，其脉宽Pw=50 ns、上升沿和下降沿Tr =Tf =1 ns。其电压幅值自0.5 V开始，在0.5～445 V范围内逐渐增大，每一个TLP电压幅值都开展一次TLP应力测试。TLP自动测试系统向芯片CD4001BE“输入到地”回路自动发送一组脉冲串，同时监测瞬态电压、瞬态电流和漏电流等数据。当TLP电压幅值达到445 V时，所监测芯片CD4001BE“输入到地”引脚回路上的漏电流曲线出现的明显变化，证明芯片损毁，TLP测试停止，系统自动记录TLP脉冲应力下的相关参数。
本文还利用TLP自动测试系统，对型号为SN74LS04D的芯片的“A-GND”也是“输入到地”回路在100 ns脉冲宽度的TLP干扰下进行测试，并获得了该回路的I-V曲线数据。
2.2 芯片CD4001BE的分段线性建模
本文为了尝试构建分段线性模型，选取芯片CD4001BE“输入到地”回路在50 ns脉宽TLP作用下的I-V曲线，是芯片各回路在受到TLP干扰作用下比较典型的I-V曲线的形状。认真观察CD4001BE的“输入到地”回路通过在50 ns传输线脉冲干扰下获取的I-V曲线走势，选取7条(k1～k7)近似线性的线段作为构建I-V曲线模型的原始数据，并且这样能够满足本文尝试构建分段线性模型方法的目的，如图1所示。这7条近似线性线段共有8个拐点(P1～P8)也如图1所示。
在芯片CD4001BE“输入到地”回路在50 ns脉宽TLP作用下的I-V曲线，选取的8个拐点所对应的每一组瞬态电压和瞬态电流值如表1所示。所对应的电阻值是根据分段线性建模原理，利用每一组数据所对应的线段斜率进行计算得出的。
表 1 模型中的参数拐点 瞬态电压(V) 瞬态电流(A) 电阻(Ω) 0 0 0 – 1 31.8 0.050 1 634.730 5 2 44 0.429 –602.532 1 3 102 3.79 –14.941 7 4 113 4.34 2.743 231 5 125 4.88 2.222 222 6 136 5.31 3.359 173 7 75.1 6.69 –69.711 83 根据上述数据，构建了芯片CD4001BE“输入到地”回路在50 ns脉宽TLP作用下的I-V曲线的分段线性仿真模型，如图2所示，其中直流电流源为瞬态电流值，二端口网络为具有正阻二极管特性或者负阻二极管特性的网络，电阻值就是对应表1中的参数。
根据基于TLP测试的实际仿真模型进行仿真得到的仿真结果(红线)与TLP实际测试的结果(蓝线)进行比对，如图3所示，可以看出两条曲线基本吻合，说明该模型能够有效地模拟TLP测试得到的I-V曲线。
如果想要在更多细节上实现更好的吻合，提高拟合度，可增加更多级的电路进行模型的完善。
2.3 芯片SN74LS04D的分段线性建模
本文还选取了反相器芯片SN74LS04D的“1A_GND”“输入到地”回路在100ns脉冲宽度的TLP干扰下的I-V特性曲线，这是一种形状相对比较复杂的I-V曲线类型，来进一步验证模型的可行性。依据芯片CD4001BE上“输入到地”回路在50 ns脉冲宽度的TLP干扰下的上述建模方法，构建了反相器芯片SN74LS04D的“A_GND”也是“输入到地”回路在100 ns脉冲宽度的TLP干扰下的I-V特性仿真模型。
如图4所示两个结果可以看出，基于器件分段线性建模仿真方法，构建反相器芯片SN74LS04D的“输入到地”回路在100 ns脉冲宽度的TLP干扰下的模型仿真以后，仿真与实测数据拟合效果很好，说明该方法具有很强的通用性，可用于后续的协同防护仿真设计中。
3. 基于等效电路的TVS二极管建模方法
本节的模型主要以文献[28]中的稳压二级管的等效电路(如图5所示)为基础，并对其进行改进来开展本研究中TVS管的建模方法研究。
TVS二极管在防护时一般是与被保护器件并联连接，这样当TVS二极管的两端受到反向瞬态高能量冲击时，能在极快(纳秒量级)的时间内将两端的电压钳制在一个预定范围，能够有效地保护集成电路中的精密器件，使其免遭损坏，其伏安特性主要包括正向偏置区、反向电流区、击穿后偏置区和电流限制区等4个区域。
3.1 TVS二极管SMDJ13A的建模
结合TVS二极管的等效电路，依据数据手册中TVS二极管的伏安特性，本节构建了TVS二极管SMDJ13A的仿真电路模型，如图6所示。
通过TVS二极管SMDJ13A的等效电路仿真得到的I-V曲线与基于TLP方法的实测数据比对如图7所示，可以看出两者有较好的拟合。
3.2 TVS二极管SMDJ40A的建模
依据TVS二极管等效电路，本节还构建了TVS二极管SMDJ40A的仿真电路模型。
通过TVS二极管SMDJ40A的等效电路仿真得到的I-V曲线与基于TLP方法的实测数据的比对如图8所示，可以看出两者有较好的拟合。
击穿电压参数是二极管器件I-V曲线中关键的拐点。器件SMDJ13A及SMDJ40A的DATASHEET中的数据、建模仿真结果以及测试结果I-V曲线中关键拐点参数击穿电压如表2所示。
表 2 TVS 二极管击穿电压参数对比(V)序号 TVS型号 数据手册的击穿
电压实测击穿
电压仿真击穿
电压1 SMDJ13A 14.4～15.9 16.31 16.57 2 SMDJ40A 44.1～49.1 47.8 47.52 从上述数据可以看出：防护器件TVS二极管SMDJ13A的击穿电压参数，实测和仿真结果相似，并且均略高于数据手册中的击穿电压范围；而防护器件SMDJ40A的实测和仿真的击穿电压值相似，且属于数据手册中击穿电压范围。由此可见，本文的实测结果、建模仿真结果与数据手册中的击穿电压参数略有差异，但基本相符，具备以此为基础继续后续研究的条件。
最大钳位电压参数是TVS二极管在防护设计中判断防护能力的重要参数。器件SMDJ13A及SMDJ40A的DATASHEET中的数据、建模仿真结果以及测试结果I-V曲线中最大电压参数如表3所示。
表 3 TVS 二极管最大钳位电压参数对比(V)序号 TVS型号 数据手册的
钳位电压实测钳位电压 仿真钳位电压 1 SMDJ13A 21.5 17.0 19.5 2 SMDJ40A 64.5 50.3 52.0 用户在使用数据手册给出的最大钳位电压值时，为了避免出现器件损坏或者降级风险，要考虑一定裕度。本文中的实测和仿真中的限制电压值均小于最大钳位电压值，这样的偏差不影响对其被保护电路可承受的瞬态安全电压的判断，因此对于芯片选型和防护设计均不会出现风险性影响。
4. 基于分段线性模型的芯片协同防护设计方法
为了模拟芯片在TVS二极管防护下应对静电放电干扰的情况，本文提出了基于分段线性模型的芯片协同防护设计方法。本文所提出的芯片协同防护设计方法就是将第2节和第3节所提出的两种类型的模型进行联合，模拟芯片在特定TVS二极管防护下的防护特性，这一方法预期可以有效地降低设计的时间和成本，提高防护设计方案的有效性。
4.1 芯片CD4001BE的协同防护设计
应用上述的芯片协同防护设计方法，本节以芯片CD4001BE“输入到地”回路为例，构建了芯片CD4001BE“输入到地”回路在50 ns脉宽TLP作用下在TVS二极管防护下的协同防护设计模型，如图9所示。
芯片CD4001BE的协同防护设计模型包括芯片本身在50 ns脉宽TLP干扰下的模型和TVS二极管等效电路模型。
经过多轮不同参数TVS二极管的迭代仿真，以及初步分析，选取钳位电压为13 V、型号为SMDJ13A的TVS二极管对CD4001BE的“B-Vss”回路进行防护，如图10。
通过进一步验证，所选取的TVS二极管在瞬态电压为16.8 V时开启防护，此时对CD4001BE的B-Vss回路在一定干扰范围内起到了防护的作用，将瞬态电压限制在17 V左右。当瞬态电压为16.8 V、瞬态电流为1.78 A的开启点之前，TVS二极管处于反向漏电区，芯片处于正常状态。当瞬态电压为16.8 V、瞬态电流为1.78 A之后直至瞬态电压为17.1 V、瞬态电流为11 A，TVS二极管处于击穿后偏置区，吸收了大电流，使电压稳定，因受到TVS二极管的防护，此时芯片仍处于正常状态。
4.2 芯片SN74LS04D的协同防护设计
应用上述的芯片协同防护设计方法，本节以芯片SN74LS04D“输入到地”回路为例，构建了芯片SN74LS04D“输入到地”回路在100 ns脉宽TLP作用下的协同防护设计模型。
芯片SN74LS04D的协同防护设计模型包括芯片本身在100 ns脉宽TLP干扰下的模型和TVS二极管等效电路模型。
经过多轮不同参数TVS二极管的迭代仿真，以及初步分析，选取钳位电压为40 V、型号为SMDJ40A的TVS二极管对SN74LS04D的“A-GND”回路进行防护。
如图11所示，芯片SN74LS04D“输入到地”回路在SMDJ40A防护下的协同防护仿真与实测的I-V曲线结果中，在瞬态电压为20 V左右之前产生了一定的偏差，之后差异逐渐减小并趋于吻合。由于芯片模型和TVS模型中均有电流源，导致它们在级联之后相互影响，出现了一定的差异。而这一差异不影响对TVS防护效果的判断。
TVS二极管的数据手册提供的参数值虽然具有参考性，但是也存在一定的偏差，而TVS二极管的正确选型对于芯片的防护是一个非常关键的因素。因此，通过协同防护设计方法具有必要性，它可以实现先行应用仿真的方法进行摸底提出选型建议，再进行实际测试验证，从而节约了设计时间和成本，进一步提高了防护的有效性。
5. 结束语
本文通过I-V特性曲线数据，构建了芯片“B-Vss”回路在TLP应力下的I-V特性模型。本文还基于数据手册数据构建了TVS二极管等效电路模型。同时，本文基于上述两个模型，提出了芯片的协同防护仿真设计建模方法，从而能够预先了解TVS防护方案的有效性，对TVS二极管的正确选型提供有效的帮助，降低了设计时间和解决成本。
致谢 感谢ESDEMC公司在TLP测试过程中提供的帮助。
-
[2] BRABHAM D C. Crowdsourcing the public participation process for planning projects[J]. Planning Theory, 2009, 8(3): 242-262. HOWE J. The rise of crowdsourcing[J]. Wired Magazine, 2016, 14(6): 1-4. RUI Lanlan, ZHANG Pan, HUANG Haoqiu, et al. Reputation-based incentive mechanisms in crowdsourcing [J]. Journal of Electronics & Information Technology, 2016, 38(7): 1808-1815. doi: 10.11999/JEIT151095. SHI Zhan, XIN Yu, SUN Yue, et al. An allocation mechanism based on the reliability of users for crowdsourcing systems[J]. Journal of Computer Applications, 2017, 37(9): 2449-2453. FENG Jianhong. Key techniques of crowdsourced query processing[D]. [Ph.D. dissertation], Tinghua University, 2015. [6] LI Yu, YIU Manlung, and XU Wenjian. Oriented online route recommendation for spatial crowdsourcing task workers[C]. 14th International Symposium on Advances in Spatial and Temporal Database, SSTD 2015, HongKong, China, 2015: 137-156. doi: 10.1007/978-3-319-22363-6_8. TONG Yongxin, YUAN Ye, CHENG Yurong, et al. Survey on spatiotemporal crowdsourced data management tecllniques[J]. Journal of Software, 2017, 28(1): 35-58. doi: 10.13328/j.cnki.jos.005140. SONG Tianshu, TONG Yongxin, WANG Libin, et al. Online task assignment for three types of objects under spatial crowdsourcing environment[J]. Journal of Software, 2017, 28(3): 611-630. doi: 10.13328/j.cnki.jos.005166. [9] CHENG Peng, LIAN Xiang, CHEN Lei, et al. Task assignment on multi-skill oriented spatial crowdsourcing[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(8): 2201-2215. doi: 10.1109/TKDE.2016.2550041. [10] HASSAN U U and CURRY E. Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning[J]. Expert Systems with Applications, 2016, 58: 36-56. [11] TONG Yongxin, SHE Jieying, DING Bolin, et al. Online mobile micro-task allocation in spatial crowdsourcing[C]. 2016 IEEE 32nd International Conference on Data Engineering, 2016: 49-60. doi: 10.1109/ICDE.2016.7498228. [12] XUE Andyyuan, ZHANG Rui, ZHENG Yu, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]. 2013 IEEE 29th International Conference on Data Engineering, 2013: 254-265. doi: 10.1109/ICDE.2013.6544830. YANG Hang. Research on prediction of trajectories of moving objects based on historical information[D]. [Master dissertation], Guangxi Normal University, 2016. SONG Xiaoyu, SUN Yeting, and SUN Huanliang. CYPK- KNN: A modified monitoring KNN queries over moving objects algorithm[J]. Journal of Shenyang Jianzhu University (Natural Science), 2006, 22(6): 1004-1007. DENG Bin. K-nearnest neighbors query algorithm in weighted uncertain graph[D]. [Master dissertation], Shanghai Ocean University, 2015. NIU Jianguang, CHEN Luo, ZHAO Liang, et al. Processing continuous K nearest neighbor queries on highly dynamic moving objects[J]. Computer Science, 2011, 38(3): 182-186. -
下载:
计量
- 文章访问数: 1577
- HTML全文浏览量: 238
- PDF下载量: 63
- 被引次数: 0
下载:
