Efficient sensor ranking mechanism for range-basedsensor search

QI Jing, WEN Yumei

(1.Research Center of Sensors and Instruments, College of Optoelectronic Engineering, Chongqing University, Chongqing 400044, P.R.China; 2.Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065,P.R. China)

Efficientsensorrankingmechanismforrange-basedsensorsearch

QI Jing1,2, WEN Yumei1

(1.Research Center of Sensors and Instruments, College of Optoelectronic Engineering, Chongqing University, Chongqing 400044, P.R.China; 2.Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065,P.R. China)

Nowadays, massive object-attached sensors have been connected to the Internet, which makes the range-based sensor search a promising service in the Internet of Things(IoT). Accessing all available sensors to find sought targets would lead to tremendous communication overhead, thus we propose an efficient sensor ranking mechanism to enhance the performance of sensor search system. The low-cost approximate representation method is designed to represent sensor output and reduce the reporting energy cost. Then based on the reported data a time-dependent prediction method is presented to estimate the future sensor measurements. Furthermore, a ranking method is given to evaluate the match degree of a sensor with the search query. Simulation results demonstrate that our mechanism can largely save energy consumption and reduce the communication overhead.

Internet of Things; sensor search; range-based; sensor ranking

1 Introduction

The booming developments of embedded sensor technique, wireless communication technology, and information processing theory contribute to the emergence of Internet of Things (IoT)[1]. The IoT is such an integrated information system that aims at perceiving and connecting the world. However, classical search engines, such as Baidu, Yahoo, and Google, are primarily used to search for static or slowly varying unstructured content like web pages, pdf, and doc files[2], rather than real-world objects. Until recently, massive object-attached sensors have been connected to the Internet, such that the real-world objects can be accessed through the attached sensors. Some novel services like pachube.com, Xively[3], and Microsoft SenseWeb[4], offer APIs for publishing structured sensor data about their state on the Internet. The Bicing[5]is a public bicycle-sharing system in Barcelona, which enables the user to obtain the number of available bicycles via the deployed sensors. Those above developments prompt the sensor search to be a promising service in the IoT.

The search target in the IoT is the object-attached sensor whose state is rapidly changing. In order to ensure the reliable of the search results, verifying the current state of available sensors is needed[6]. However, accessing all deployed sensors would result in tremendous communication overhead. A further enormous challenge is that the majority of existing search systems lack the support of the search mode with a given measurement range. Because the readings of most sensors deployed in the IoT are numerical values. Besides, sensor measurements always slightly fluctuate over time as the state of monitored entity usually changes quickly and marginally. Hence, searching for sensors based on a specific value is of limited benefit. Therefore, the range-based search system was proposed in[8] so that the user can search for the sensor whose output meets a query range instead of a specific value. However, the research works on range-based sensor search technology are very limited.

2 Related work

In recent years, several sensor search systems have been proposed, such as MAX[7], Snoogle[8]and Microsearch[9]. They are based on keyword match and only support the search for pseudostatic metadata. Hence, they fail to retrieve dynamic sensor measurements. Besides, whenever the search engine responds to a search query, it needs to access all available sensors to locate match ones, which leads to huge communication overhead.

To reduce the communication overhead, a sensor state prediction method was proposed in Dyser[10]to efficiently search for real-world entities. However, Dyser assumes that sensor readings utilized by the prediction method is not raw sensor measurement but high-level state and always present a high degree of periodicity, which might be limited in some application scenarios where sensors can only output quantitative values.

In response to above problems, a sensor search system CSS was proposed in[6]. CSS supports the range-based sensor search mode and without any assumptions about periodicity in sensor data. A light-weight sensor state prediction method, based on fuzzy logic, is applied in CSS to estimate the probability that a sensor matches with a given search content. However, the prediction method of CSS is time-independent, which is unable to accurately present the latest trend of sensor state. Moreover, the prediction method of CSS is built by the sensor itself, which implies CSS assumes that sensors have powerful computing capacity and energy resources. That might be impractical because sensors usually own limited computing capacity and energy resources.

Therefore, we propose an efficient sensor ranking mechanism (ESRM) to solve those above problems. The main contributions of this paper include the followings:

1)An architecture of range-based sensor search system is designed to meet the low-cost search needs. The search process of ESRM is more reasonable than the existing systems. The major computing tasks of the prediction method are assigned to the gateway rather than sensors, which is practical in most application scenarios.

2)A sensor ranking mechanism is proposed to improve the search efficiency. We introduce the Piecewise Linear Representation method to represent the sensor state values which need to be reported to the gateway, in order to reduce the reporting energy cost. Then we present our sensor state prediction method based on the state-of-the-art time-dependent regression prediction theory. At last, we design a ranking method to efficiently perform the verification process.

3 System design

In this part we depict the architecture of our sensor search system and present the main components, including the functions of each component. Then we design the interactive processes between these components in ESRM. ESRM consists of four types of modules: client, gateway, database, and WSN. The user can submit a sensor search query via the client. We define the search query as the combination of a variety of information, such as the geographical location, the type of desired sensors, search range and so on. For example, the search query can be “Paris, temperature, [a,b](tq)”, which denotes that the user desires to search for the place where temperature readings satisfy the range [a,b] at timetqin Paris. The architecture of ESRM is depicted as Fig.1.

Fig.1 Architecture of ESRM

The gateways distribute across the Internet in a layered structure. The upper gateway responds to the search query and issues the query to appropriate lower gateways, according to the query items provided by the user. The lower gateway receives the approximated sensor state values reported by the sensor and predicts the future state values for all of its managed sensors periodically. Each database is associated with a lower gateway and stores those predictive values.

At first, the sensor periodically collects the state values of its attached real-world object. Then it uses the approximate representation method proposed below to fit the collected values and reports them to the lower gateway. The lower gateway then utilizes our prediction method to estimate the future sensor readings for each of its managed sensors based on the reported values, and stores these values in its relevant database. When a search query arrives, the upper gateway issues the search commands to suited lower gateways after resolving the query items submitted by the user. Then the lower gateway initiates a match query to its associated database in order to find candidate sensors which satisfy the search range. After that, the lower gateway sends a local ranking list to the upper gateway. Then the upper gateway reorders these lists and publishes verifying commands to lower gateways to selectively verify the actual state of a certain number of candidate sensors. Afterwards, the lower gateway transmits the verification results to the upper gateway, which would merge these results and return the final search results to the user. The search process is designed in Fig.2 as follows.

Fig.2 Interaction process of sensor search

4 Sensor ranking mechanism

In this part, we propose a sensor ranking mechanism, including the approximate representation method, the time-dependent prediction method, and the ranking method. The approximate representation method is proposed to fit the collected sensor state values for reducing the reporting energy cost. The time-dependent prediction method is presented to estimate the future sensor state. The ranking method is designed to evaluate the match degree of a sensor with the query range. When a search query arrives, our mechanism would rank sensors that have higher matching degree on the top. Only top sensors should be verified, rather than all available targets. Thus the communication overhead of the search system can be obviously reduced.

4.1 Approximate representation method

As mentioned above, the prediction method predicts the future sensor readings based on some historical measurements. Thus sensors should periodically collect the state values and report to the lower gateway. The collecting frequency is usually much larger than the reporting frequency, which means the sensor needs to consume much energy to transmit all these collected values. We propose the approximate representation method by utilizing the Piecewise Linear Representation (PLR) theory to solve this problem. PLR is about the approximation of a time seriesT, of lengthn, withKstraight lines. BecauseKis typically much smaller thann, this approximation would largely reduce the transmission of the data and save a lot of energy for the sensor. As most of the sensors in the IoT have limited computing and energy resources, we cannot assign complex computing tasks to the sensor. Therefore, we adopt the Bottom-Up algorithm[11]to approximate these collected values. The approximate representation method is described below.

Step2We respectively calculate the approximating error of merging each adjacent segment and record the pairjandj+1 which has the minimum approximating error.

Step3We compare the approximating errorej,j+1of the pairjandj+1 with the predefined thresholdε. Ifej,j+1≤εthen we merge the pairjandj+1 to a new segmentjnewand go to Step 2. Otherwise, the algorithm should be terminated.

From the algorithm described above, we deduce that the computation complexity of approximation method isO(Ln) whereLdenotes the average length of segments.

4.2 Time-dependent prediction method

As discussed above, the existing sensor state prediction method is time-independent and fails to accurately perceive the temporal correlations between sensor data. Therefore, we propose the prediction method based on the least squares support vector machines (LS-SVM)[12], which is the state-of-the-art time-dependent regression prediction theory.

The prediction function initially can be described as

f(x)=ωTφ(x)+b

(1)

whereω,ω∈Ηis the weight vector of the feature space andbdenotes the offset. Theφ(x),φ(x):Rn→Ηis a nonlinear mapping function. To improve the generalization capability of prediction function, based on Structural Risk Minimization principle we further describe the prediction function as

(2)

In (2)Jis the loss function andγ,γ>0 means balance coefficient. Denoteeito be the prediction error. The above problem can be transformed into the following equation by introducing the Lagrange function as

(3)

whereαidenotes the lagrangian multiplier. According to the KTT and Mercer conditions, we can obtain the matrix equation as follows

(4)

In (4)y=[y1,…,yn]Tandα=[α1,…,αn]T.Iis then×ndimensional identity matrix andΩ=φ(xi)Tφ(xj) denotesn×ndimensional kernel function matrix. The estimation of the parameter [b,α]Tcan be acquired by using least square method. We use the radial basic function (RBF) as our kernel function, and then the sensor state prediction functionf(x) finally can be deduced as

(5)

After the lower gateway receives the approximated values reported by the sensor, it will use our prediction method to estimate the future sensor output at any query time of the next reporting period.

4.3 Ranking method

Obviously, based on the predictive values estimated by the above prediction method, we can easily find candidate sensors whose predictive values would fall into the query range. However, distinguishing a more suitable sensor from those candidate ones is quite unintuitive. Besides, the number of sensors sought by the user is usually limited. Thus we only need to verify some of these candidate sensors rather than all of them. Therefore, we propose the ranking method to assess the match degree of a sensor with the search query.

Denotef(x)tqto be the predictive sensor state value of a sensor at the query timetq. We assume that the query range is [a,b]. Then the match degreeMdcan be calculated as

(6)

After we obtain the match degree of all the sensors, we rank them in descending order. Thus only the top-ranking sensors need to be verified by the gateway and the communication overhead can be definitely reduced.

5 Performance evaluation

In this section we use two real-world datasets, which are IntelLab[13]and NOAA[14], to evaluate the performance of our sensor ranking mechanism. IntelLab contains 54 temperature sensors deployed in the Intel Berkeley Research lab. NOAA consists of 87 water temperature sensors deployed along the coast of America. The search range [a,b] is randomized within the minimum and the maximum value of the dataset. The query timetqis randomly distributed within [1,n]. We propose the energy consumption ratio, which means the reporting energy cost after approximating to that before approximating, to evaluate the performance of approximation method. Then we introduce the communication overhead, which is proportional to the number of sensors that should be accessed, to examine the performance of ESRM and CSS mentioned above. We perform the experiments on a PC with Intel Core i7 CPU and 8 GB RAM under MATLAB 2014a. Each simulation result is the average of running for 50 times.

From Fig.3 and Fig.4 we see that the energy consumption ratio decreases with the maximum error percentage growing. This is because the growing maximum error percentage reduces the average number of segments, which further lowers the amount of data reported to the lower gateway. Thus the reporting energy cost would be reduced. We also note that our approximation method can respectively save the energy consumption about 48.4% for IntelLab and 55.8% for NOAA than the data transmission process without using the approximation method.

Fig.3 Energy consumption ratio performance for IntelLab

In Fig.5 and Fig.6, we find that the communication overhead of ESRM keeps relatively stable while CSS presents a large degree of volatility. That is because our prediction method has an excellent generalization capability. The prediction accuracy of ESRM will not largely fluctuate. Thus the communication overhead of ESRM remains stable. However, the prediction method of CSS is time-independent which considers the change law of sensor data in the current period just the same as that of the preceding two periods. So CSS fails to fully perceive the temporal correlations between sensor data and accurately predict the future sensor output. We also note that ESRM respectively reduces the communication overhead about 19.1% for IntelLab and 20.7% for NOAA than that of CSS. That is because our prediction method can better perceive the variation trend of sensor data by exploiting temporal correlations between sensor output values to enhance the prediction accuracy of future sensor readings. Then our ranking method can rank more match sensors which have higher match degree on the top. The local gateway only needs to verify the top sensors to check their actual state. Therefore, ESRM can greatly reduce the communication overhead than CSS.

Fig.4 Energy consumption ratio performance for NOAA

Fig.5 Communication overhead with different simulated days for IntelLab

6 Conclusions

In this paper we propose an efficient sensor ranking mechanism to enhance the efficiency of sensor search system. A low computation complexity approximation representation method is presented to fit the collected sensor output values and reduce the reporting energy cost. Then a time-dependent prediction method is designed to accurately assess the future sensor readings. Moreover, a ranking method is proposed to estimate the match degree of a sensor with the query content. Simulation results demonstrate that our ESRM mechanism can achieve excellent performance in terms of energy consumption and communication overhead. In the future, we plan to improve our prediction method based on deep learning theory.

Fig.6 Communication overhead with different simulated days for NOAA

[1] CHEN Y, ZHOU J, GUO M. A context-aware search system for Internet of Things based on hierarchical context model[J]. Telecommunication Systems, 2016, 62(1):77-91.

[2] TANG W, YAN L, YANG Z, et al. Improved document ranking in ontology-based document search engine using evidential reasoning[J].Iet Software,2014,8(1):33-41.

[3] LogMeln. Giving customers radiant flooring control anytime,anywhere[EB/OL]. [2016-09-11]. https://xively.com.

[4] KANSAL A, NATH S, LIU J, et al. SenseWeb: An Infrastructure for Shared Sensing[J]. Multimedia IEEE, 2007, 14(4):8-13.

[5] ZHANG P, LIU Y A, WU F, et al. Matching State Estimation Scheme for Content-Based Sensor Search in the Web of Things[J]. International Journal of Distributed Sensor Networks, 2015, 2015(6):1-12.

[6] TRUONG C, RÖMER K. Content-based sensor search for the Web of Things[C]// Global Communications Conference. Atlanta, GA, USA：IEEE, 2013:2654-2660.

[7] YAP K K, SRINIVASAN V, MOTANI M. MAX: Wide area human-centric search of the physical world[J]. Acm Transactions on Sensor Networks, 2008, 4(4):1-34.

[8] WANG H, TAN C C, LI Q. Snoogle: A Search Engine for Pervasive Environments[J]. Parallel & Distributed Systems IEEE Transactions on, 2010, 21(8):1188-1202.

[9] TAN C C, SHENG B, WANG H, et al. Microsearch: A search engine for embedded devices used in pervasive computing[J]. Acm Transactions on Embedded Computing Systems, 2010, 9(4):43.

[10] OSTERMAIER B, RÖMER K, MATTERN F, et al. A real-time search engine for the Web of Things[J]. Internet of Things, 2010, 9(2):1-8.

[11] KEOGH E. SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACH[M]// Data Mining In Time Series Databases. [s.l.]: World Scientific, 2003:1-21.

[12] BRABANTER K D, BRABANTER J D, SUYKENS J A K, et al. Optimized fixed-size kernel models for large data sets[J]. Computational Statistics & Data Analysis, 2010, 54(6):1484-1504.

[13] Samuel Madden. Intel Lab Data[EB/OL]. [2016-09-13]. http://db.csail.mit.edu/labdata/labdata.html.

[14] Center for Operational Oceanographic Products & Services (CO-OPS). NOAA/NOS/CO-OPS-ODIN MAP[EB/OL]. [2016-09-12]. http://tidesandcurrents.noaa.gov/gmap3.

Biographies:

QI Jing (1983-) was born in Jiangxi Province, China. He received the BE degreein Electrical & Information Engineering from Chongqing University of Posts and Telecommunications in 2005, and the ME degree in Electrical & Information Engineering from Chongqing University in 2008. Now, he is working towards his PHD in School of Chongqing University. His research interests include sensors and instrumentation, energy harvesting circuit, short distance wireless communication, sensor search. E-mail:qijing@cqupt.edu.cn.

WEN Yumei(1964-) was born in Chongqing, China. She received the BE degree in electrical engineering from Beijing Aeronautic and Astronautic University in 1984, the ME degree in electrical engineering from China Academy of Launch Vehicle Technology in 1987, and the PhD degree in instrumentation engineering from Chongqing University in 1997. She has been a professor at College of Optoelectronic Engineering in Chongqing University since 1998. Her research interests include sensors and instrumentation, signal processing, energy harvesting devices, and LED lighting.

(编辑：魏琴芳)

基于距离相关的高效传感器排名机制研究

漆 晶1,2,文玉梅1

(1.重庆大学 光电工程学院，重庆 400044; 2.重庆邮电大学 移动通信重点实验室，重庆 400060)

随着越来越多的物理实体传感器被接入互联网，在此基础上延伸出的物联网应用中，基于距离相关的传感器搜索服务有着广阔的发展前景。对于实现传感器数据的访问以找到所寻求的目标过程，将导致巨大的通信开销，因此，提出了一个高效的传感器排名机制，以提高传感器搜索服务系统的性能; 设计了低成本的近似表示法应用于表示传感器的输出端，从而降低传感器的发射能耗。然后，根据上报的传感器数据建立一个随时间变化的预测模型，基于该模型预测传感器未来数据的输出; 还提出了一种排名方法用来评估与搜索查询的传感器的匹配程度。仿真结果表明，提出的传感器排名机制可以在很大程度上节约能耗，减少通信开销，具备较好的使用价值。

物联网；传感器搜索；距离相关；传感器排名

2016-10-23

2017-09-06

漆 晶 qijing@cqupt.edu.cn

重庆市教委科学技术研究项目(KJ1500433)；重庆邮电大学自然科学基金 (A2012-97)

TP212.1DocumentcodeAArticleID1673-825X(2017)05-0704-07

The Science and Technology Project Affiliated to the Education Department of Chongqing Municipality(KJ1500433)；The Natural Science Foundation of Chongqing University of Posts and Telecommunications(A2012-97)

10.3979/j.issn.1673-825X.2017.05.018