简介

这个学期我选了老板Mobile & Pervasive Computing这门课，要求学生每周精读两篇论文，学生轮流做Presentation。具体论文列表和时间安排可以在这里（进去后点“Calendar and Lecture Notes”）找到。读了这些文章以后，受此文启发，我把看过的论文和相应的总结列出来。这些论文大多是MobiSys, MobiComp或OSDI上与移动计算相关的会议文章，应该说代表了该领域的最新研究进展。

这门课把"移动和普适计算”这个领域分成10个子话题，分别是：Profiling （性能分析），Wireless Networking （无线网络），Localization （定位），Cars and Homes （汽车和家庭应用），Enabling Continous Sensing （低能耗传感器应用 ），Participatory Sensing （ 传感数据收集与分析），Developing World （移动计算在发展中国家的应用），Privacy （隐私），Security（安全）和Mobile Cloud （移动 + 云） 。 我选了以下四个话题，共8篇论文，简要介绍它们所做的研究状况和个人的见解，希望能对国内的移动计算研究人员有所帮助。

Profiling （性能分析）
What is keeping my phone awake? Characterizing and Detecting No-Sleep Energy Bugs in Smartphone Apps
Abhinav Pathak, Abhilash Jindal, Y. Charlie Hu, Samuel P. Midkiff
MobiSys 2012

论文作者来自Purdue大学的Charile Hu教授和他的研究组。他们组近几年来在energy profiling 和energy bugs上做了不少研究，发了好几篇论文。例如同样是2012年的Pathak et al. Where is the energy spent inside my app?: fine grained energy accounting on smartphones with Eprof。

这篇论文关注的是手机app中的能耗缺限（energy bug）。众所周知，手机的电池寿命很短，而手机上的一些部件是耗电大户，例如摄像头，开发者写代码时理应做到非诚勿扰，不用请关闭。如果程序员没有正确地使用API，调用了手机的部件（acquire）而忘记了释放(release)，那么就会导致那个部件一直处在开启的状态，造成了不必要的消耗。这可能就是打开某些app后手机很快就会变烫的原因。

为了了解energy bug的在实际代码中的普遍性，作者们首先去手机论坛上寻找相关的帖子或bug report。他们开发了一个爬虫器（crawler），自动爬了近一百二十万个帖子。同时，他们还去bug list和开源代码库去寻找与能耗相关的bug。最后他们还用自己写的bug detector去自动扫描app的源代码。此间的工作量真惊人，但皇天不负有心人，终于有所发现。

作者们的工作很细致，兢兢业业地把找到的bug分成了三类：（1）no-sleep code path: 意即某个手机部件（例如摄像头）的wakelock被占有，但程序员用完后忘记了释放它，造成了部件处于一直开启的状态。三个原因导致了这种情况，一是程序员由于粗心，在acquire了某个资源以后，忘记写release()代码了； 二是程序执行路径有很多，程序员可能记得在 if 分支写了release 代码，但在else 分支却忘记写了，这种情况在代码量很大时很常见； 第三个原因就是程序员没有正确地理解Android的API，例如你把release 代码放在了onDestroy() 方法里，以为手机app 关闭时app就会释放这个资源，但是Android的app 是只有在手机的内存很低，才会被完全地停止的，写在了onDestroy() 方法里代码可能要经过相关长的时间才会被调用的，而资源被释放得不及时的话，能耗就被白白地浪费了。（2）no-sleep race condition: 在多线程情况下，程序员可能把资源的获取（acquire）代码写在了线程1，而把释放release的代码写在了线程2里，正常情况下就按“获取=>释放”这个节奏跑的，可是线程调度并不一定按程序员臆想的顺序跑，有可能线程2执行在了线程1前面，这样就造成了“先释放，再获取”的顺序，资源就不会被释放了。（3）no-sleep dilation:  就是一段代码在获取和释放中间经历了太长时间，反映在代码里，就是acquire和release 之间夹杂了太多的代码，资源没有得到及时释放，也会造成浪费。

在把bug分成了这三类以后，作者们开发出一个bug的自动检测器，希望能在app发布之前就把bug检测出来。作者用的是软件测试的经典技术：数据流分析法。大概就是把每个资源看成一个变量，把acquire和release都看成是一种对变量的定义（definition）。检测bug的问题就转化成，去检测程序执行路径的终点，看是不是每个变量（即资源）都以被release的状态离开的，如果不是，那就说明这个变量被acquire了后没有被翻译，这就是一个bug。详情请参考论文的6.1小节。

方法的关键在于它的自动化，只要静态的代码分析就可以得出结果。同时也在启示我们，数据流分析法原来可以这么用。

AppInsight: Mobile App Performance Monitoring in the Wild
Lenin Ravindranath, Jitendra Padhye, Sharad Agarwal, Ratul Mahajan, Ian Obermiller, Shahin Shayandeh
OSDI 2012

论文作者来自微软研究院。本文关注的问题如何提高手机软件的用户体验。影响用户体验的一个重要因素就是手机软件的响应速度。app能快速正确地响应用户操作，才会让这个app用起来清爽凉快。天下武功，唯快不破嘛。

如果知道用户在使用你开发app时，软件到底卡在哪几个环节上，然后想办法优化那个费时耗力的环节，这样就可以提高运行速度了。一般的手机app上交互是很频繁的（highly interactive），开发者在具体实现的时候都会用异步（asynchronous）多线程来处理请求，所以程序具体的执行路径可能是非常复杂的，用户点击一下手机屏幕上的按钮可能就会触发N个线程，不是一般的复杂。

本来这应该是app开发者们的事，要收据用户数据，就要在app里实现相应的数据收集功能。但是开发这些功能并不一定会为公司会带来实实在在的利益，如果不是那种实力雄厚的大公司，一般的开发团队是没这个闲情去干这种劳神费力的事的。

微软的这几位作者就这么光荣地扛起了大旗。他们的目标是（1）不“扰民”，不用改动开发者原有的代码，仅在已经编译好的app 二进制执行文件（binary）里动手脚 ，插装（instrument）他们的性能跟踪功能模块； （2） 插装的模块一定要小而快，不能对原来app的性能有太大的影响。（3）不能对原来的OS有改动，立即可以部署运行。

于是他们就鼓捣出了AppInsight。AppInsight是的原型是在Silverlight框架上实现的，windows app很多都是在这个框架上开发的。原代码在Silverlight框架上写好后，就会被编译成MSIL的字节码（byte code），MSIL码里有很多程序的数据，包括类型，方法名和类继承关系等等。文中并没有给出很详细的技术细节，照我理理解，AppInsight 大概就在MSIL码里插入自己的logging和detour代码。

装了AppInsight的app, 能够监测app的实时线程信息。现在手机上的app是用单个线程来处理用户界面UI的，所有界面上的更新都在这个UI线程上处理，所以一般的App为了提高响应速度，都尽可能把一些计算量大的或者有网络延迟的任务交给其他线程去做。基于这点观察，插装的这个模块要收集的数据就有（1）在哪个时刻产生了UI事件，（2）在哪个时刻app的执行是在多个线程里执行的，（3）异步调用和回调（asynchronous call and callback）间的因果关系，（4）线程的同步时间（5）在哪个时刻UI得到更新，（6）是否有未处理的exception.

为了得到这6种数据，AppInsight会在UI的线程里加入logging和detour代码，在每个UI线程中调用其他线程代码的前一行和后一行插入logging方法，在回调代码的方法里也插入logging。叙述起来太啰嗦，具体的插入代码实例可以参照文中的Figure 7.

作为初步实验，作者们把AppInsight插装在30个windows app上，在志愿者的手机上运行了4个月，收集了很多数据，带给开发者有很多反馈。但好像效果一般，文章仅具体描述了三例AppInsigh如何帮助开发者, 而且其中第三例还说得语焉不详，不知道AppInsight到底得到了什么insight. 另外，AppInsight 是在windows phone 上实现的，不知道在Android上实现类似的东西是否可行。

Participatory Sensing （ 传感数据收集与分析）
PEIR, the personal environmental impact report, as a platform for participatory sensing systems research
Min Mun, Sasank Reddy, Katie Shilton, Nathan Yau, Jeff Burke, Deborah Estrin, Mark Hansen, Eric Howard, Ruth West, and Peter Boda,
MobiSys 2009

论文作者来自UCLA和Nokia北美研究院。此文关注的是如何从人们日常生活中自动地收集地理信息数据（其实就是GPS坐标），然后根据这些数据计算个人行为对环境的影响（impact)，以及个人在多大程度上暴露在不健康的环境下（exposure）。他们提出的PEIR系统原型，可以自动收集志愿者的手机GPS在某个时段的连续读数，用机器学习的方法来判断志愿者是否在步行 （walking）或者驾驶（driving）的状态； 下一步，结合当前上下文（context）背景数据，包括温度、湿度天气，当前路况、城市地图等，PEIR能计算志愿者当前行为的impact 和 exposure，（1）因交通产生的碳排放量（transportation-related carbon impact）(2) PM2.5接触程度，（3）在敏感区域（例如医院、学校）中PM2.5的排放量（PM2.5 output near sensitive sites）（4）垃圾食品的接触程度（fast-food exposure）。

第四个指标垃圾食品的接触程度很有意思，是基于一个经济学的统计成果[5]提出来的，结论大概是，肥胖率与个人跟垃圾食品的接近程度（proximity to fast food）成正比，此结论用在儿童身上尤其明显。也就是说，你长胖的原因之一，可能是你家离麦当劳太近了，这家店影响了你的饮食选择，导致有很大的概率你会把垃圾食品放入口中。

现代人们都在追求低碳、绿色、环保的生活，PEIR系统正好迎合了这种愿望。想象一下，早上开车去上班前，你打开手机上的PEIR,  它会告诉你走解放路是最低碳的，而走南京路产生的PM2.5排放会最高； 好友小芳今天上班经过了26家快餐店前，她有68%的概率会吃上垃圾食品，增长1-3斤，然后你慢慢扬起邪恶的嘴角……

回到正题，此论文的意义在于，它提供了一个自动收集、建模、处理和分析用户移动设备数据的实际案例。个人认为，其亮点在于系统的自动化，将个体的数据和上下文context数据结合起来，得出有用的结论。文中发表的时间是2009年，那时可能 big data 这个词还没有火起来，所以这文章没有用这个词，但我认为他们做的系统就是“大数据”时代的一个典型应用，移动设备和各种传感器已经开始深入到人们生活各个方面的，将来的移动的 app 如何分析和使用这些大量的数据，在此文中可一窥端倪。

里面的问题和挑战也不少，例如人们日常的行为是复杂的，依据简单GPS的读数到底能不能准确地预测行为呢？连作者在做trip segmentation的时候也承认，人们的复杂行为模式让trip的持续时间（duration）很难预测。另外，文中的模型也仅考虑了步行和驾驶两种行为状态而已，略显简单了一些，能不能建立更加贴合实际、能给出更有用的结论的模型，还尚属未知。

参考文献：[5] E.Moretti J.Currie, S.DellaVigna and V.Pathania.The effect of fast food restaurants on obesity. Working Paper 14721, National Bureau of Economic Research, February 2009.


Crowdsourcing to Smartphones: Incentive Mechanism Design for Mobile Phone Sensing
Dejun Yang, Guoliang Xue, Xi Fang, Jian Tang
Mobicom 2012

论文作者来自Arizona State University, 从作者上判断他们应该都是华人。此文关注的是如何设计激励机制（incentive mechanism），让更多的移动用户来参与到传感数据收集的活动中来。文章提出了两种模型，以用户为中（user-centric）和以平台为中心（platform-centric） 模型，分别用了Auction theory和Stackelberg game 理论来设计，都是很经典的经济学理论。

该论文实质是那两个经济学理论在移动计算里的应用，数学很多，相对来说口味略重，很久没在mobile 或 system的文章里看到数明定理证明了。那两个经济学理论不在我的研究范围之内，我就不好妄言了。

Security（安全）

Distinguishing Users with Capacitive Touch Communication
Tam Vu, Akash Baid, Simon Gao, Marco Gruteser, Richard Howard, Janne Lindqvist, Predrag Spasojevic, Jeffrey Walling
Mobicom 2012

作者们来自纽约州的Rutgers University. 这篇论文提出的是一项新用户识别技术，它利用现有的电容性触屏硬件设备，在人体中再加一个很小的外加设备（在实验中用的是一个小指环），当用户的手指一触碰屏幕的时候，软件能自动识别这个用户，用户就不必再输入密码了。这项技术背后就是利用人体作为导体，当用户身体触碰到屏幕时，从那个小小的设备里产生微弱电流信号就能透过人体传到屏幕上，用于识别是哪个用户在触碰屏幕。

当然，要真正实现这项技术，背后的难点还有很多。 第一个难点是，他们现有的原型做得会有延迟，就是用户手指要触摸屏幕一段时间后，屏幕会真正感知到这个事件，这可能会影响用户体验。这个限制是因为他们的识别算是根据 事件的数量（the number of events）来算的，他们会设定一个阈值（threshold），超过了这个阈值的事件才会被感知到。这个算法在我看来还有提高空间，还可以从硬件层面做更好的支持。第二，他们的系统原型有两种交互方式，一种是直接方式，让指环直接接触屏幕，第二种是间接方式，指环不必接触屏幕，用户手指碰到屏幕就行了。第二种间接的交互方式比较新颖一点，理想情况下，戴着指环的用户一点屏幕，屏幕就知道这是谁了，连密码都不用输入。但现实是，他们现在只做到屏幕仅能检测到当前用户是否带了指环，而不读取指环内部芯片传来的数据，这是因为人体皮肤的电阻太大，指环产生的电流经过人体、再传到屏幕上时，非常不稳定，无法将数据准确无误地传到屏幕那方的接收器上。所以，现在的技术只能检测到两种用户：戴指环的和不戴指环的，而不能知道这个用户到底是谁。

还有其他相关技术，例如NFC（http://www.kickstarter.com/projects/mclear/nfc-ring），成本也不高，只要离手机10cm就可以识别出用户，发展的前景看似会更好一些。

CleanOS: Limiting Mobile Data Exposure with Idle Eviction
Yang Tang, Phillip Ames, Sravan Bhamidipati, Ashish Bijlani, Roxana Geambasu, Nikhil Sarda
OSDI 2012

本文作者来自哥伦比亚大学。他们的平台是基于TaintDroid做的。项目背景是这样的，现在手机上储存了越来越多的个人信息，一旦手机被偷了（调查报告称纽约地区有49%的市民有过手机被盗的经历，在中国这个概率可能更大），会技术的不法分子可以从还在运行的手机里提取出敏感信息，例如用户名和密码、银行账号等。这些信息之所以有可能会被盗取，是因为很多Android app 在开发的时候就是把这些信息存在一个变量里，然后这个变量一直存在手机里。有几个原因导致了这种情况，（1）删除不彻底（insecure deletion），常见的情况就是，一些内核或java框架里的代码有bug，忘记释放某个指针，导致那些关键敏感信息一直尘封某个内存角落里，带来安全隐患；（2）app 会把这个变量存在RAM里，连加密都没有，例如作者们发现，很多App把email的密码声明成一个全局变量，然后它就大摇大摆白底黑字常驻在内存里了。理论上，不法分子扫一扫内存就能提取出这些信息来。（3）内存泄露（memory leaks）。

因此，为了防止像email密码这些敏感信息被技艺高超的不法分子用非法手段获得，作者们就想出了CleanOS这种系统。首先，他们用TaintDroid 这种低层的跟踪技术，把内存中包含敏感信息的变量都“涂上标志”（来，跟我一起唱“我是一个粉刷匠/粉刷本领强……”），如果程序过了一段时间都没有访问这些tainted的变量，系统就会自动将这些变量加密，然后把密钥上传（evict）到相应的云（Cloud）服务。注意，这时本地手机内存里还放在这个变量数据，只不过是加了密的数据，但没有密钥，没有人知道他们具体是什么值。如果过了一会程序又要访问这个变量了，由于变量已经加密了，不能够从本地获得那个变量的值，于是就请求云里把密钥发回来，立即解密，程序又可以与原来的变量值重逢了。

这项技术为何能提高手机的安全性呢？例如你发现你的手机，在这个情况下，你可以立即通知那个存储了你所有密钥的云服务，让它停止发送所有密钥到手机上。如此一来，没有了密钥，手机内存上的敏感信息都是加密过的，不法分子根本不知道你的密码是什么，从而保护了你的安全。

想法是挺好的，但这项技术还是会有一些问题（以下问题是由非常聪明的Mike Qin同学提出）。第一，此技术只能保护内存上的敏感信息，可是如今硬件有多级缓存（cache）的，再加上OS可能人把你的内存有若干个copy,  所以你的敏感信息只在内存上加了密，但没准在哪个缓存上它还是原封不动地那儿，这种情况虽然少，但是一种隐患，至少在理论上存在这种可能的。第二，CleanOS太过于依赖于云了。那些号称很安全的云服务本身也有安全隐患，NSA一个眼色使过来，Google或Microsoft们能不就范？所以要用户把自己的密钥上传到安全性值得怀疑的云上，用户会放心吗？（3） 过于依赖wifi 或3g，这点在文章中也提到了，例如手机处在飞行模式时，没有ｗｉｆｉ，无法从云里下载密钥，这时我的程序要用内存上的已加密的数据，那怎么办？虽说可以暂时把密钥下载存在手机上，用户会觉得麻烦先不说，这也会造成安全隐患，Mike就在课上喊道：在飞机上手机被偷了怎么办？

所以嘛，即使用了CleanOS, 手机的安全问题还尚未解决的。在我看来，问题的根源之一，就是app开发者把一些不必要的敏感数据保存在了内存里，如果我们能够用TaintDroid去让开发者意识到这个问题，app的安全性可能会提高。所以，这也可以是软件工程开发实践的研究问题（不自觉又回到水水的软工了……囧）。

Mobile Cloud （移动 + 云)

MAUI: Making Smarthphones Last Longer with Code Offload
Eduador Cuervo, Aruna Balasubramanian, Dae-ki Cho, Alec Wolman, Stefan Saroiu, Ranveer Chandra, Paramvir Bahl
MobiSys 2010

COMET: Code Offload by Migrating Execution Transparently
Mark S. Gordon, D. Anoushe Jamshidi, Scott Mahlke, and Z. Morley Mao, Xu Chen,
OSDI 2012
 
这两篇论文讲的方面有点相似，我就放在一起讨论了。两篇文章关注的是如何把手机上的计算（computing）转移（offload）到服务器上。为何要offload呢？一般来说，因为手持设备体积小，在上面的硬件限制很多，无论cpu, 内存和硬盘都有限，一些计算量需求很大的任务（例如人脸识别、实时图像处理等），如果把任务转移到有更强大硬件支持的server上，任务计算完后再把结果发回到手机端上，当然比你在手机上运行这些任务更快，既可以提高任务完成的速度，也可以节省手机能源。这两篇论文就是以此为出发点的。

MAUI系统原型出现得早一些，在2010年就被来自Duke, UCLA,  UMas 和 MSR 的作者们实现了。大意是这样，让移动开发者在开发app的时候，在原有代码上添加一些标识，例如methodA的过程是适应off-load到server上运行的，那么你就在上面加一个特定的annotation。下一步就由MUAI的编译器处理了。在运行的时候，MUAI 会自动根据当前的网络情况、再结过去的运行历史来判断这个方法是在本地运行，还是被off-load到server. 文章是跟MSR合作的，系统自然是在Windows phone 上做的。

COMET 系统也实现了类似的功能，但它更加自动化，不用麻烦开发者自己去手动标识app上的代码，系统在运行时（run-time）里动了手脚，能自动地决定是否offload.  COMET用到的技术是分布式共享内存（distributed shared memory），就是能够让移动设备和服务器端共享一个地址内存空间，允许线程（thread）自由迁移。为了维持手机上的和服务器上的内存一致，两端要同步。显然，维持两份一样的内存的开销是很大的，任何一个变量的值在手机运行时被程序修改了，服务器上相应的变量也要改变，这之间产生的同步通信会影响网络带宽。这个问题在分布式计算领域里估计也这算最基础的问题了。COMET 采取的策略是，用一个lock 机制来避免资源冲突，跟OS里的信号量是一个道理。另外，为了减少手机和服务器上的同步通信，它们线程上的更新一直积累到 lock 被另一端的获得到后才更新。这个机制也是利用了程序的局部性（locality），也就是说，很多线程都只会访问一小部分内存。如果手机上的线程1和服务器上的线程2所用的内存页面是完全不相干的，那么即使它们运行时有页面更新，也不必立即就同步所有的页面，需要的时候再同步就行了。那什么时候是“需要的时候”呢？ 就是从手机上迁移到服务器上的（或者反方向的）线程要访问手机上的内存时，我们才把那些累积的更新一次性同步就行了。这样会大大减少两端的同步通信频率。

回到文章出发点：提高手机app运行速度和节省能耗。从他们的实验结果来看，他们貌似达到了。在他们的benchmark testing里, 如果手机附近有一个wifi off-load server，MAUI 能把人脸识别识别程序从19秒的运行时间降到了2秒，运行时的能耗也节省了超过5/6，运行其他两个程序时的效果相对差一点，也能提高一些速度和节省能耗（具体请参考文中的fig. 9 和 fig. 10).  COMET的效果也差不多，不过用的benchmark 测试集不一样，无法直接与MUAI 对比。

idea是挺酷的，但挑战也不少。MUAI要开发者自己手动去标识程序，这点很烦人我就不说了。off-load很重要的一点就是如何设计一个scheduler, 它的设计很关键，因为它会实时决定是否把程序offload, 如果你的设计不好，把不该off-load的off-load了，你是达不到优化的效果的，举个极端例子，你可以让sheduler 把手机上的计算任务全部都迁移到服务器上运行，那么出现什么情况？带宽受不了！ 除非你有1Tbps超过bus总线的极速网络(弱弱问一句：这在将来可能实现么？)，你靠那100Mbps的破wifi 来把手机上的所有的内存、寄存器值、硬盘等数据传到服务器……金将军，等结果传回来的时候，惠乔都老了。

因此，scheduler的设计很关键，什么该off-load, 什么不该off-load，需要看实际情况来定，在这点上，MUAI 和COMET有一个共同点，就是利用历史数据来预测方法或线程的执行时间。预测的准确率是一个问题。另一个问题是网络的速度是实时变化的。MUAI的作者们做过实验，如果wifi的往返延迟RTT（round-trip time）小于10ms 时，节省能耗效果最好，而RTT超100ms时效果可能会适得其反，比原来在手机上单独运行时会更耗电（估计是因为用wifi传数据损失的电量比在手机本地上直接运行任务的能耗还要大），所以scheduler要依据实时的数据变化来调整off-load的策略，一些不太critical的任务在网络不好的时候就不要off-load了，否则得不偿失。3G网络的Offload就是典型例子，比你没有offload的效果还差很多。

这样看来，因为wifi bandwidth的限制，能够off-load的task 或者thread都是有限制的。再者，目前的程序也没有几个是适合off-load的,  MUAI用了一个人脸检测程序作为例子，COMET 用的是一些computing benchmark 的测试集（还不是真正的手机app)，offload后的效果会好一点,也就是说，offload后能有速度提升和节省能耗，而其他的手机app测试，效果只是一般（fig9, fig10),  估计是因为它们也不算是计算量很大（computation-intensive）的程序，还有相当一部分的UI任务（例如用户触屏的响应程序）是不适宜转到服务器上运行的，真正需要很强力的cpu去执行。至少目前的app里这样computation-intensive 的app还很少。当然，COMET的作者在最后也argue, 将COMET出来以后, computation-intensive app会多起来的，因为COMET提供了这种可能性。

老板在上课的最后还提到了一个形而上学的思考命题：到底off-loading这种不分界限(with no boundary)计算模型是否适合手机呢？先解释一下何谓“不分界限”（no boundary），就是计算任务既可以在手机上进行，也可以在服务器上进行的。相对地，我们传统的用的是Web模型 就是一种有界限的计算机模型，有前台和后台，就是说什么是应该在客户端（浏览器）运行的，什么是该在服务器后台运行的，界限是很分明的。而off-loading 不分前台和后台，一有可能就offload， 这种模型就会产生了上述的scheduler的设计问题。


个人声明:
1. 本文讨论的8篇论文都来自Dr. Eyal de Lara的paper list, 选材的credit 归他。
2. 论文总结和摘要都是本人所写，若有词汇翻译或理解不当之处，欢迎指出！
3. 转载或引用请注明出处，谢谢！