Jaime Moreno

Alessandro Rizzi

Christine Fernandez-Maloigne

A NEW METRIC OF IMAGE QUALITY ASSESSMENT FOR STEREOSCOPIC CONTENT

Keywords: Stereoscopic image quality, Quality assessment databases, 2D image quality

Automatic or semi-automatic stereoscopic image quality assessment has arisen due to the recent diffusion of a new generation of stereoscopic technologies and content demand. Thereby, there is a growth in asking for algorithms of Stereoscopic Image Quality Metrics (SIQA). In this paper, we present a method for assessing the stereoscopic image quality, QUALITAS. QUALITAS is grounded on some human visual system features such as contrast sensitivity, effect of disparate image quality in left and right images, and distance perception, which do not depend on the images being tested. QUALITAS is defined in five stages. Instead of averaging individual qualities of the stereo-pair, QUALITAS introduces Contrast Band-Pass Filtering on a wavelet domain at both views, namely our algorithm perceptually weights left and right images depending on certain viewing conditions. This paper includes the comparison of 27 Metrics SIQA proposed by 16 authors, which summarizes the work made in this field in the recent five years, on image database LIVE 3D. Some algorithms can be combined with any 2D/Normal Image Quality Assessments (NIQA), giving as a result that QUALITAS was compared against 221 Metrics. QUALITAS obtained the best results in terms of overall performance of correlation coefficients. We conclude all metrics in SIQA-SET are simple modifications of NIQA, which take into account some extra characteristics from the disparity map (usually depth variances). Instead QUALITAS incorporates disparity masking in addition to divide 3D scenario in two parts: background and foreground planes. Moreover QUALITAS employs a contrast bandpass filtering, so dynamic parameters are considered as observational distance. It includes loss of correlation, luminance and contrast distortion. It takes into account the visual differences between left and right images, employing a penalization depending on their wavelet energy. Thus, the novelty of QUALITAS lies in combining some the best features of stereoscopic image quality assessments.

INTRODUCTION

Figure 1 depicts a general scheme of stereoscopic imaging, which is divided in three blocks objective assessment (in green), subjective assessment (in blue), and strength of relationship (in red). Objective assessment is a subsystem constituted by the following parts: 1) Input: Left and right images. 2) Process: Stereoscopic coding.

3) Output: Stereoscopic image. 4) Feedback: Stereoscopic image quality assessment (SIQA).

Bertalanffy in [START_REF] Bertalanffy | Teoría General de los Sistemas[END_REF] proposed the general systems theory, which describes that Feedback verifies how efficient the Process is. So, the main goal of the SIQA is to measure in the stereoscopic image either image quality or degradation of the original stereo-pair whereas for the process of stereoscopic Coding is to obtain the least possible degradation of the original stereo-pair. In other words, any kind stereoscopic image coder employed in 3D Cinema, for instance, needs to support its results using a SIQA. This lead us to mention that the recent growth of stereoscopic algorithms goes hand in hand to the growth of the way to predict its quality. Thereby, the algorithms that assess the quality of a stereoscopic image has gained great importance. It is reasonable to base SIQA from NIQA, since the observers employed in psychophysical experiments or subjective assessments [START_REF] Goldmann | Impact of Acquisition Distortion on the Quality of Stereoscopic Images[END_REF], [START_REF] Wang | Research on subjective stereoscopic image quality assessment[END_REF], [START_REF] Akhter | No-referencestereoscopic image quality assessment[END_REF] evaluate image quality from different slices in 2D scenario, which depend of the apparent distance.

STEREOSCOPIC IMAGE QUALITY ASSESSMENTS

OBJECTIVE ASSESSMENTS

From Figure 1 (green block, Objective Assessment), the main goal of any the stereoscopic image quality is to predict a subjective response, namely finding a predicted MOS (MOSp). Then, Table I shows the 27 stereoscopic metrics from 16 authors, this set of 27 metrics will be call henceforth SIQA-SET. It is worth noting that some authors propose more than one metric and we maintain the metric name that they gave them. Thus, we eventually will refer to a certain metric by the name that appears in the corresponding row, not by its author. Also, SIQA-SET was coded ourselves in MatLab.

Table 1. Stereoscopic image quality assessments. SUBJECTIVE ASSESSMENTS

In the field of subjective stereoscopic image quality assessment, few image databases have been developed. We have employed LIVE 3D stereoscopic image database of the Laboratory for Image and Video Engineering of the University of Texas at Austin (USA. LIVE 3D contains standardized psychophysical experiments [40] and their stereoscopic images quality data are based on observer opinion score, collected with individual quality judgments, in Figure 1 the blue block Subjective Assessment). In each trial, the images are rated on a scale of excellent, good, fair, poor, and bad. Then, by means of statistical procedures, the data are processed, finally obtaining the mean opinion scores (MOS). Each stereoscopic image database applies different statistical procedures; the reader can refer to the citation for the details. Additionally, MOS merges results of different types in a form that allows the comparison with any kind of stereoscopic assessment metric. Since SIQA predicts subjective responses, namely it obtains a predicted MOS or MOSp.

EXPERIMENTAL RESULTS

From Figure 1 Any correlation coefficient value close to 1 indicates good correlation with human perception, while lower values of RMSE indicate better performance.

Table 2 shows the performance of an overall experimental result, which includes all SIQA of the SIQA-SET in addition to QUALITAS. Thus, QUALITAS correlates in 93.92% and 76.68%, Figure 11, being the metric that obtains the best LCC and KROCC, respectively. In terms of SROCC, the best ranking metric is d2 UQI, since it is best with 93.35%. Also, based on these results, DQmap2 is the most accurate metric not only for all set of distortions considered but also for JPEG2000 and JPEG distortions. Regarding only these image compressiondistortions, QUALITAS is the best ranking metric in both distortions obtaining the highest correlation in both rank ordered coefficients.

CONCLUSIONS

This paper includes the comparison of 27 Metrics SIQA proposed by 16 authors, which summarizes the work made in this field in the recent five years. Some algorithms can be combined with any NIQA, giving as a result that QUALITAS was compared against 221 Metrics.

QUALITAS obtained the best results in terms of overall performance of correlation coefficients either LCC, SROCC or KROCC with 93.92%, 93.34% (just 0.01% below the best one), and 76.68%. For Root Mean Squared Error, QUALITAS did not get the best results, because it was developed with the aim of increasing any kind of correlation coefficient at certain times sacrificing accuracy.

Figure 1 .

 1 Figure 1. Block diagram of a general system for stereoscopic assessing.

  red block, strength of relationship between normalized MOS and MOSp is measured by a Performance Measure (PM), such as correlation coefficient. Strength of relationship gauges how strong is the tendency of two variables to move in the same or opposite direction. The performance measures used are: • Spearman's Rank Ordered Correlation Coefficient (SROCC), • Kendall's Rank Ordered Correlation Coefficient (KROCC), • Pearson's Linear Correlation Coefficient (LCC) and • Root-Mean-Squared Error (RMSE).

Table 2 .

 2 Overall performance across SIQA-SET including QUALITAS in predicting perceived stereoscopic image quality.

We conclude all metrics in SIQA-SET are simple modifications of NIQA, which take in to account some extra characteristics from the disparity map (usually depth variances). Instead QUALITAS incorporates disparity masking in addition to divide 3D scenario in two parts: background and foreground planes.


Mahdi Elvis Vogli

Mahdi Ben Alaya

Thierry Monteil

Luigi Alfredo Grieco

Khalil Drira
email: khalil@laas.fr

An efficient resource naming for enabling constrained devices in SmartM2M architecture

Keywords: 6LoWPAN, CoAP, ETSI, IoT, M2M, SmartM2M, REST

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

The Internet of Things (IoT) represents, in the context of networking and services, one of the most relevant innovations of the third millennium [1], [START_REF] Atzori | The internet of things: A survey[END_REF]. The vision of this new paradigm is a world-wide network with a tremendous amount of heterogeneous interconnected objects where all the types of real-world physical elements (sensors, actuators, personal electronic devices, or home appliances) are able to autonomously interact with each other. The IoT defines in other words a cyber-physical system that enables many advanced applications, either in domestic (i.e, domotics, assisted living, e-health etc.) or in industry domain (i.e, automation, logistics, manufacturing, intelligent transportation etc.). At the same time, the IoT entails an unprecedented gamut of new technical challenges, only partially addressed so far [START_REF] Whitmore | The internet of things-a survey of topics and trends[END_REF], [START_REF] Li | The internet of things: a survey[END_REF].

In this context, low power and short range wireless communication technologies play a key role since they can enable the creation of spontaneous, pervasive, and energy efficient communication networks of smart nodes. Such technologies are commonly adopted in Wireless Sensor Networks (WSNs) and Machine-to-Machine (M2M) systems [START_REF] Chen | Machine-to-machine communications: Technologies and challenges[END_REF]. The standard with the longest-standing impact is IEEE 802.15.4 [START_REF]Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF], which defines a low-power Physical (PHY), and a Medium Access Control (MAC) layer, which has been the foundation of ZigBee [START_REF][END_REF]. This standard has been extended by its new IEEE 802.15.4e amendment [8]. Among other features, it introduces the Time Slotted Channel Hopping (TSCH) mode to increase the reliability and the energy efficiency of short range wireless communications in noisy environments [START_REF] Tang | Channel characterization and link quality assessment of ieee 802.15.4-compliant radio for factory environments[END_REF]. Moreover various Internet Engineering Task Force (IETF) Working Groups (WGs) facilitate the integration of low-power wireless networks into the Internet and define a complete IoT stack for WSN [START_REF] Palattella | Standardized Protocol Stack for the Internet of (Important) Things[END_REF]. The IPv6 over Low power Wireless Personal Area Networks (6LoWPAN) WG [START_REF] Kushalnagar | IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals, RFC 4919[END_REF] defined an adaptation layer that compresses the IPv6 header to make it suitable for constrained networks. The IPv6 over Networks of Resourceconstrained Nodes (6lo) WG focuses on the work that facilitates IPv6 connectivity over constrained node networks. The Routing Over Low power and Lossy networks (ROLL) WG has defined the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) a routing protocol for WSN [START_REF] Winter | RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks[END_REF]. Finally the Constrained RESTful Environments (CORE) WG has defined The Constrained Application Protocol (CoAP) a lightweight protocol which enables Representational State Transfer (REST) architecture in constraint devices.

Many other component-level standards exist, addressing different radio interfaces or different networking choices. Each choice is optimized for a particular application scenario therefore many vertical M2M solutions have been designed independently. This inevitably hinders a large-scale M2M deployment. Therefore the largest part of the challenge facing the M2M actors is to transform vertical silos into a set of easily developable and incrementally deployable applications. This in term has brought to the deployment of horizontal platforms. What is meant by "horizontal" is a coherent framework valid across a large variety of business domains, networks, and devices. This horizontal middleware layer makes the data independent from the network access, which in term facilitates the interoperability among different network technologies.

To this end, the European Telecommunications Standards Institute (ETSI) has been working to define a set of specifications which provide a RESTful architecture able to standardize the way heterogeneous devices can offer services and access to them seamlessly [START_REF] Elloumi | M2M Communications: A Systems Approach[END_REF]. Such platform facilitates the deployment of vertical applications and boosts innovation across industries for an effective interoperability. Therefore a device which uses REST application protocol like HyperText Transfer Protocol (HTTP) or CoAP should not have problems interacting with the ETSI M2M platform. This however is not straight forward when it comes to constrained devices like the 6LoWPAN sensor/actuator devices.

In this paper we analyze the application registration phase of 6LoWPAN constrained devices in an ETSI SmartM2M platform and the impact of the URI is highlighted. Considering that hierarchical resource names produce long URIs, an efficient and non hierarchical resource structure was proposed and evaluated. In particular, it is demonstrated that the URIs in the proposed solution are shorter with fixed length and the number of messages required in the initialization phase is smaller, making this solution better suited for constrained devices.

The rest of the paper is organized as follows. In Sec. II,at first an overview on ETSI SmartM2M architecture and the resource registration phase is given, than it is described the the protocol stack of the constrained devices. In Sec. III it is described a non hierarchical schema for M2M resources to reduce the overall length of URIs. Sec. IV are evaluated the proposed solutions in comparison with the standardized SmartM2M approach. Finally, Sec. V gives the conclusions and future works II. AN OVERVIEW ON ETSI M2M STANDARD According to the Global Standards Collaboration Machineto-Machine Task Force, more than 140 organizations around the world are involved in M2M standardization. A considerable effort is done by ETSI to decrease M2M market fragmentation by defining a horizontal service platform for M2M interoperability. The proposed solution provides a RESTful Service Capability Layer (SCL) [14] accessible via open interfaces to enable developing services and applications independently of the underlying network. A SCL interfaces the network access from the application domain. Each device has to register the resources in the SmartM2M standard platform which in turn can be accessed from the applications from SmartM2M platform in a seamless way.

Figure 1 describes the SmartM2M functional architecture. An SCL can be deployed on an M2M Network (NSCL), a Gateway (GSCL), or a Device (DSCL). It provides several service capabilities to enable machine registration, synchronous and asynchronous communication, resource discovery, access rights management, group broadcast, etc. An M2M Device runs applications using the SCL. It can connect directly to the Network Domain via the Access network and may provide service to other devices connected to it that are hidden from the Network Domain. It can also be connected to the Network Domain via a Gateway through a Local Area Network. A Gateway also runs M2M Applications using the SCL, and can act as a proxy between local devices and the network domain.

The access network allows M2M devices and gateways to communicate with the Core Network. The SCL provides functions that can be shared by different Applications. Network Management Functions enables to manage the Access and Core Networks, such as Provisioning, Supervision, and Fault Management. M2M Management Functions consist of all the functions required to manage the SCL in the Network Domain.

Three reference points [START_REF]IEEE Standard for Local and Metropolitan Area Networks -Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs) Amendment 1: MAC Sublayer, IEEE Std[END_REF] based on open APIs are specified: mIa, dIa, and mId. The mIa reference point allows a Network Application (NA) to access the NSCL. The dIa allows a Device or Gateway Application (D/GA) to access the D/GSCL. The mId reference point allows a D/GSCL to access the NSCL. These interfaces are defined in a generic way to support a wide range of network technologies and protocols to enhance interoperability. SmartM2M adopts a RESTful architecture style. Each SCL contains a standardized resource tree where the information is stored. A resource is uniquely addressable via a URI, and has a representation that can be transferred and manipulated with verbs (e.g. retrieve, update, delete, and execute).

An SCL resources tree supports different kind of resources. The "sclBase" resource describes the hosting SCL, and is the root for all other resources within the hosting SCL. The "scl" resource stores information related to distant SCLs, residing on other machines, after successful mutual authentication. The "application" resource stores information about the application after a successful registration on the hosting SCL. The "container" resource acts as a mediator for data buffering to enable data exchange between applications and SCLs. The "contentInstance" resource represents a data instance in the container. The "accessRight" resource manages permissions and permissions holders to limit and protect the access to the resource tree structure. The "group" resource enhances resources tree operations by adding the grouping feature. The "registration" resource allows subscribers to receive asynchronous notification when an event happens such as the reception of new sensor event or the creation, update, or delete of a resource. The "announced" resource contains a partial representation of a resource in a remote SCL to simplify discovery request on distributed SCLs. The "discovery" resource acts as a search engine for resources. The collection resource groups common resources together. A partial view of the resource tree is shown in Figure 2.

In this work the OM2M project [START_REF] Alaya | Om2m: Extensible etsi-compliant {M2M} service platform with selfconfiguration capability[END_REF], which provides a complete open source implementation of the SmartM2M standard including both the server and the gateway part will be used to validate the proposed approaches. The main concern of this contribution is focused in connecting constrained devices (i.e., 6LoWPAN based wireless sensor network) to the Gateway over the dIa interface.

A. Device Application Gateway SCL registration

Each Device Application (DA) should register to its Gateway SCL. The registration phase can be divided in three parts. In the first part, an "Application" resource is created. In the second part it is created a description "container" where are stored descriptive information related to the application. Finally in the last part there is created a data "container" where are stored the application data (i.e., sensor or actuator data).

In Table I there are described the messages that an example application called TEMPERATURE will send to the G/NSCL as defined in ETSI SmartM2M standard. After each POST message a new resource in the resource tree will] be created. In particular there are created the highlighted resources shown in Fig. 2. The first message sent will create TEMPERATURE application resource accessed through the /gscl/applications URI. The second message will create a DESCRIPTOR container with URI /gscl/applications/TEMPERATURE/containers which will contain a content instance created from the third message. The third message will provide descriptions and semantics related to the created application accessed through the URI /gscl/applications/TEMPERATURE/containers/DESCRIPTOR-/contentInstances. The fourth message will create a DATA container resource with URI /gscl/applications /TEMPERATURE/containers/DATA which will hold content instances created from the fifth message. And finally, the fifth will send to the SCL the sensor data which are stored in /gscl/applications/TEMPERATURE/containers/DATA/content-Instances. The last message will be sent from the DA each time it needs to communicate a new sensor value.

B. Overview on the WSN stack

The protocol stack depicted in Figure 3(a) represents one of the most promising stacks for IoT. Above the efficient 802.15.4(e) MAC the Internet connectivity is obtained thanks to 6LoWPAN which enables IPv6 addressing in constrained devices. In addition the CoAP application protocol provides a RESTful protocol for constrained devices. Despite the fact that this stack is designed to be implemented in M2M scenarios their integration is not a simple task. A major constraint is imposed from the packet length where the MAC layer limits the maximum frame length to 127 bytes.

If we consider the headers of each of the protocols in the depicted stack, in the application layer will barely be available 50 Bytes. Neither one of the messages depicted in Tab. I) can be transmitted in a single frame, therefore fragmentation mechanisms should be used. The use of fragmentation in the link layer or at the IP layer to enable the transport of larger representations is possible, but the fragmentation and successively the reassembly is a burden on the lower layers of resource constrained devices and can be more efficiently managed in the CoAP layer.

In CoAP there are defined Block options which provide a way to transfer large representations in block-wise fashion. Using these options, larger resource representations can be fragmented and reassembled by CoAP independently of the lower layers as well as the above applications. In Figure 3(b) it is described the format of CoAP packets.

The header of fixed length of four bytes is followed from a token with size that can be up to 8 bytes. Than there are a set of several options. Finally there is the payload which should always be preceded from payload delimiter option (0xFF byte). Despite the existence of all the mechanisms necessary for the transfer of long representations the long URI length of the resources defined in the ETSI SmartM2M standard could become a relevant issue. The URI are sent as options in the CoAP header and should be present in each block. If it is very long there will not be possible to send the block in only one message and the further datagram fragmentation will be needed.

In the case of the ETSI SmartM2M resource tree as it can be seen from the Figure 2 there are up to six different levels of the URI which can make the overall length particularly long. In some cases it not be possible to send in a single datagram CoAP blocks even if it is used the minimum block size (16 byte) due to the length of the URI. This example clearly shows the necessity for optimal design of URIs in order to improve the efficiency in constrained devices.

III. MODELS

The SmartM2M standard has descriptive naming conventions for the resources such that the meaning of each resource can be clearly conveyed and understood. Some of these names are very long and in addition, the fact that the resource structure is hierarchical (i.e., tree like resource structure), as it can be verified from the Table I, can generate very long overall URIs. In the second version of the SmartM2M standard [17], in order to cope with constrained devices, there were introduced as an informative annex shorter naming conventions for resource and attributes. In particular resource names which are long only two byte and shorter attribute names are provided. The first one tend to minimize the URI length whether the second one have an impact on the payload data representation length. This short alias where defined appositely to cope with limitation imposed from constrained devices.

In Fig. 4 it is described the registration phase using the short resource names and structure provided from SmartM2M. The resource names provided from SmartM2M are respectively the resources in the level two, four and six in the resource tree of the Figure 2. Instead for the user defined resources have been considered three byte long names. For each request sent from the device application, the gateway will send back the resource created in the confirmation response. It can be clearly noticed that this approach provides shorter URIs compared to the standard descriptive names. However, despite the short length of the resources, the hierarchal resource structure sets a limit on the overall URI length. In the case there is retrieved a content instance which is in the seventh level, only for the path separator character (/) will be needed 7 bytes.

A. Non Hierarchical URI model

Previously we have shown an example about SmartM2M with up to seven nested resources but in general this number can be bigger. To overcome the limitations imposed form the hierarchical resource structure defined in ETSI SmartM2M hereby we propose a flat non hierarchical resource structure.

We propose a new approach which limits the number of nested resources and therefore optimizes the overall URI length. In particular we distinguish two cases depending on the type of request message that will be used. In the first case, in the POST messages that will be used to create new resources the structure of the URI will be: /<prefix>/<resource_id>/<suffix> Each URI will have to three levels called "prefix", "re-source_id" and "suffix". In order to create a new resource a POST request should be made to a URI having the aforementioned structure. The generic URI of the created resources will be:

/<prefix>/<resource_id>

The "prefix" of the resource created should be the "suffix" of the URI in the POST message used to create the resource. Moreover the resource URI will be the generic URI structure that will be used with the other REST methods (i.e., GET, PUT or DELETE).

In analogy to the SmartM2M example described previously in Fig. 5 there is shown the subscription phase of a device application to its gateway using the non hierarchical URI structure proposed. There are used two byte names for the "prefix" and "suffix" (the same names defined in SmartM2M) and three byte names for created resources. In the first message a POST to /SB/SCL/AP will create the TMP application resource in /AP/TMP. In the response there will be included the created resource URI to inform the DA. In the second message it is created the descriptor container by a POST message sent on the "container" collection of the TMP application. The descriptor container resource will not be nested under the collection as in the SmartM2M case instead it will respect the generic URI defined. In this case the collection of the TMP application resource will become the prefix of the descriptor container resource. Therefore the descriptor resource path will be /CO/DES and it will have its own collections nested to it. Finally, in the third message it is created the description instance by POST message sent to the contentInstance collection with URI /CO/DES/CI. Again the new resource with containing the application description will be created in /CI/DES. In the fourth and fifth message there are created the data container (/CO/DAT) and the data content instance (/CI/dat).

In this schema, once it is decided the length of a resource, the overall URIs will always have the same length. As it can be seen the URIs used in POST messages have a length of ten bytes whether the URIs used for the other methods are seven byte. The length of the resource name should be long enough to be able to address all the resources in the gateway. In addition the prefix and the suffix represent collections. The number of this collections is really limited such that only one byte can be used to represent them all. Therefore the size can be furtherly reduced with two bytes becoming eight bytes for the POST messages and six bytes for the other methods.

IV. EVALUATION

In the Tab. II and Tab. III there are compared the four different approaches which were described throughout the paper. The values shown in the table are calculated taking in consideration the following conditions. • The user defined resources for the SmartM2M hierarchical resource scheme (i.e., the first, third, fifth and seventh level resources) and the "resource_id" in the proposed scheme are considered to have all the same length equal to three bytes.

• The number of messages and the number of blocks sent are calculated taking in consideration message representation described in Tab. I.

• It is considered a CoAP block-wise transmission with blocksize 16 bytes.

• It is considered that a CoAP packet bigger than 50 bytes will be fragmented into multiple datagrams.

• Only the messages required in the registration phase and the relative URIs are considered.

In the case of the SmartM2M with long resource names the overall number of block sent in registration phase will be doubled compared to the other cases. This happens because each CoAP fragment will split in two datagrams when the payload and CoAP header and options will exceed the length of the datagram payload.

In the Table II there are shown the length of the URIs used in the five POST messages sent during the registration phase and the length of the URI used in the GET message sent to retrieve the data of the resource created. The descriptive long names produce very long URI as it can be seen form the first raw of the Table II. In addition the URI lengths of the SmarM2M structured resources will be very long in the nested resources. The GET message will address resource which is in the seventh level therefore if we compare with the first POST it will be about three times bigger. This is happening only because of the hierarchical resource structure. The non hierarchical resource structure proposed as it can be seen has a constant length among the POST messages and it has even a shorter length for the other methods.

In Table III there are evidenced the maximal URI sizes for the POST and the GET messages for the URI schema proposed and they are compared with both, the descriptive and the short named resource structure proposed defined in SmartM2M. In particular the non hierarchical names the corresponding URI is always 10 (8) bytes for POST (GET) messages whether the SmartM2M in the best case, where are used short names is 21 (25) bytes. In this situation the SmarM2M with short URIs requires the same number of messages as the proposed solutions but this scenario is not always possible. In particular if there are other options to be included in the CoAP header (i.e., like the authorization option in case there is enabled security) it is very easy that the messages will be fragmented even in the SmartM2M . In this situation it will be very easy that the CoAP length will become long enough to require the datagram fragmentation. In this context the non hierarchical URI proposed will be the choice where the spared bytes due to URI length reduction can be used to improve security or implement other functions without having to fragment the packets, or there can be used a CoAP block with a bigger size. V. CONCLUSION Machine-to-Machine communication will boost up in the near future, but connecting constrained devices is not challenging. Beside the definition of lightweight protocols a very careful design of the resource names should be done to guarantee the correct use of the constrained devices. In this paper it was shown that the hierarchical resource names can produce very long URIs which can cause an increase of datagram fragmentation. For this reason a non hierarchical schema for resource naming was proposed and it was shown that the overall URIs will be short and suited for constrained devices. Despite the optimizations made in the URI length, there is still an elevated number of messages in the subscription phase. Considering the low data rate that characterizes constrained devices (like 6LoWPAN device), the overall time required for registration can be long. In addition to a careful URI design the message formats should be thoroughly optimized in order to decrease the overall number of messages.

Fig. 1 :

 1 Fig. 1: SmartM2M high level architecture.

Fig. 2 :

 2 Fig. 2: ETSI URI resource tree structure (example).

Fig. 3 :

 3 Fig. 3: Protocol stack and CoAP format.

Fig. 4 :

 4 Fig. 4: Messages in the ETSI-M2M tree URI case.

Fig. 5 :

 5 Fig. 5: Messages in the flat URI case.

TABLE I :

 I POST messages requested for the registration of a Device application in the GSCL. Example in the OM2M implementation.

	Msg.	Content	Size
		Msg. Nr. 1 -Create an application Resource (TEMPERATURE)
	POST	/gscl/applications	18
		<om2m:application xmlns:om2m="http://uri.etsi.org/m2m"
		appId="TEMPERATURE">
		<om2m:aPoCPaths>
		<om2m:aPoCPath>
		<om2m:path>
	Payload	coap://[IPv6_Prefix::IPv6_Suffix]:5683	234
		</om2m:path>
		</om2m:aPoCPath>
		</om2m:aPoCPaths>
		</om2m:application>
		Msg. Nr. 2 -Create an DESCRIPTOR container
	POST	/gscl/applications/TEMPERATURE/containers	41
	Payload	<om2m:container xmlns:om2m="http://uri.etsi.org/m2m"	75
		om2m:id="DESCRIPTOR"/>
		</obj>
		Msg. Nr. 4 -Create an DATA container
	POST	/gscl/applications/TEMPERATURE/containers	41
	Payload	<om2m:container xmlns:om2m= ḧttp://uri.etsi.org/m2m"	70
		om2m:id="DATA"/>
		Msg. Nr. 5 -Create a content instance in the DATA container
	POST	/gscl/applications/TEMPERATURE/containers/DATA	63
		/contentInstances
	Payload	<str name="data" val="XYZ"/>	28

Msg. Nr. 3 -Create a content instance in the DESCRIPTOR container POST /gscl/applications/TEMPERATURE/containers/DESCRIPTOR 69 /contentInstances <obj> <str name="type" val="Temperature_Sensor"/> Payload <str name="location" val="Home"/> 260 <op name="getValue" href="gscl/applications /TEMPERATURE/containers/DATA/contentInstances /latest/content" is="retrieve"/> <op name="getDirectValue" href="gscl/applications /TEMPERATURE/sl" is="retrieve"/>

TABLE II :

 II URI lengths in the POST messages used in subscription phase and the GET message to retrieve the data content instance created.

		POST	POST	POST	POST	POST	GET
		Nr. 1	Nr. 2	Nr. 3	Nr. 4	Nr. 5
	SmartM2M	18	41	69	41	63	71
	Long names
	SmartM2M	7	14	21	14	21	25
	Short names
	Non-Hierarchical	10	10	10	10	10	7
	Non-Hierarchical	8	8	8	8	8	6
	One Byte names

TABLE III :

 III Maximal URI lengths and the number of frames required from each Device Application to register

		Maximal URI Length
		POST	GET, PUT	Nr. of blocks
			or DELETE	for registration
	SmartM2M	69	71	100
	Long names
	SmartM2M	21	25	50
	Short names
	Non-Hierarchical	10	7	47
	Non-Hierarchical	8	6	47
	One Byte names


Senior Member, IEEE, Mahdi Luigi Alfredo Grieco

Ben Alaya

Thierry Monteil

Khalil Drira

A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems

Keywords: Graph theory, Topology, Networks, Overlay

published or not. The documents may come

I. INTRODUCTION

Graph-based models are fundamental tools to assess, predict, and control the performance of complex systems, made of interacting dynamic units. In these systems, vertice are usually associated to the dynamic units whereas edges represent interactions. The application domains of graph-based models include coupled biological/chemical systems, social networks, software applications, and communication protocols [START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF]- [START_REF] Chen | Synchronization of complex networks with impulsive control and disconnected topology[END_REF].

In many real systems, unfortunately, the properties of their interacting units cannot be deterministically known in advance. In these cases, random graphs [START_REF] Erdos | On the evolution of random graphs[END_REF] can be fruitfully used to infer the characteristics of the topology, based on the probabilistic behavior of vertice and edges (see also [START_REF] Newman | Random graphs with arbitrary degree distributions and their applications[END_REF] for a comprehensive overview on the subject).

With reference to communication issues, random graphs have been mainly adopted to describe unstructured overlays [START_REF] Massoulie | Network awareness and failure resilience in self-organising overlay networks[END_REF]- [START_REF] Lobb | Adaptive overlay topology for mesh-based P2P-TV systems[END_REF], web properties [START_REF] Aiello | A random graph model for massive graphs[END_REF], and Internet topology [START_REF] Reittu | On the power-law random graph model of massive data networks[END_REF].

In this brief, we focus on diameter constrained overlays, i.e., virtual network topologies having a diameter no larger than a predefined threshold D. This kind of overlay is very useful to support delay sensitive applications, such as in Peerto-Peer (P2P) TV [START_REF] Veglia | Performance evaluation of P2P-TV diffusion algotihms under realistic settings[END_REF] and emerging Machine-to-Machine (M2M) systems [START_REF] Grieco | Architecting information centric ETSI-M2M systems[END_REF]. In fact, the higher the diameter D the higher the end-to-end communication delay [START_REF] Kurose | Computer Networking: A Top-Down Approach[END_REF]. The problem of building diameter constrained graphs has been thoroughly L. A. Grieco is with the Department of Electrical and Information Engineering, Politecnico di Bari, Bari, Italy, e-mail: a.grieco@poliba.it M. B. Alaya and T. Monteil are with CNRS, LAAS, and Univ. de Toulouse, Toulouse, France. K. Drira is with CNRS, LAAS, Toulouse, France. e-mail: {ben.alaya, monteil, khalil}@laas.fr afforded in [START_REF] Loguinov | Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience[END_REF] with reference to structured overlays, built upon distributed hash tables (DHT). Unfortunately, to the best of the authors' knowledge, no theoretical contribution has been formulated yet, able to describe with closed form expressions the dynamics of an unstructured evolving overlay, subject to a constraint of the maximum diameter D. This kind of model could be very useful to enable closed loop autonomic management strategies as well as to characterize, in a tractable form, both transient and steady state properties of network topologies in M2M scenarios [START_REF] Grieco | Architecting information centric ETSI-M2M systems[END_REF], [START_REF] Alaya | Autonomic computing system for self-management of machine-to-machine networks[END_REF] and beyond.

Starting from this premise, a theoretical model based on random graph is formulated herein, which considers a discrete time process of arrivals to describe the sequence of vertex couples among which a path composed of no more than D edges has to be established. Accordingly, a general topology formation mechanism M is formulated, expressing the rules that drive the addition of new edges, obeying to the constraint on the maximum diameter D. Then, exploiting the properties of the binary adjacency matrix A in graph theory [START_REF] Noel | Understanding complex network attack graphs through clustered adjacency matrices[END_REF], an original and tractable discrete time model is proposed that describes the evolution of the average network degree (i.e., the number of edges per node) subject to M and D. The model is successfully validated using computer simulations in a wide range of scenarios (with up to 2 16 nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach. They include: (i) the derivation of an approximated upper bound D √ 2 • N • lnN on graph average degree (i.e., the average number of edges per vertex); (ii) the comparison with respect to delay optimal de Bruijn graphs [START_REF] Loguinov | Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience[END_REF]; (iii) the analysis of the graph robustness; (iv) the derivation of system dynamics in presence of edge failures.

The rest of the brief is organized as follows: the main theoretical achievement is presented in Sec. II and validated in Sec. III. Useful examples of its applications are described in Sec. IV. The last Sec. V closes the brief and draws future research.

II. MODEL

A. Target Scenario and Notation

The target scenario considered in this brief consists of a graph of N vertice, n q being the q-th vertix (q ∈ [1, N ]). Furthermore, an ordered sequence of equi-probable 1 couples of vertice is considered, among which a path composed of no more than D edges has to be established. The t-th couple is described by the vertice (n it , n jt ). For sake of simplicity, the variable t will be referred to as time from now on. Knowing the t-th couple, a new edge is established in the graph if and only if the two vertice (n it , n jt ) are not reciprocally reachable in no more than D edges. Knowing, the number of edges l t-1 at time t-1, the probability that a couple of vertice at time t will not be reciprocally reachable in no more than D edges is defined as P t-1 . Notice that, since we are assuming homogeneous conditions, P t-1 is the same for all the possible couples (n it , n jt ).

Accordingly, our model is grounded on the following equation:

l t+1 = l t + P t (1)
which, considering that the average degree [START_REF] Erdos | On the evolution of random graphs[END_REF] (i.e., the number of edges per vertex) is k t = 2•lt N , can be also expressed as:

k t+1 = k t + 2 N P t (2)
The presence of an edge between any couple of vertice at time t will be expressed (as usual in graph theory) using the binary symmetric adjacency matrix To provide an illustrative example of the networked system we are modeling as a random graph, Fig. 1 shows the evolution of a graph made of N = 5 vertice and constrained by D = 2 max path length. In this example, the ordered sequence of vertice (n it , n jt ) is: (n 2 , n 4 ), (n 1 , n 4 ), (n 1 , n 2 ), (n 4 , n 5 ), (n 2 , n 3 ), and (n 1 , n 3 ). Accordingly, for each of them, a new edge is added if and only if a path shorter than 3 edges is not already available among corresponding vertice. In the sequel of the contribution, we will derive a law that rule the evolution of this kind of graphs in a general case.

A N xN t , so that A t (i, j) = A t (j, i) = 1 if

and only if an edge between n i and n j exists at time t (otherwise

A t (i, j) = A t (j, i) = 0).

B. Main result

Proposition 1. For a sufficiently large N , the following expression describes the dynamics of the average graph degree:

k t+1 ≈ k t + 2 N • exp ( - 1 N • k D+1 t -k t k t -1 ) (3)
Proof. The model considered here is based on Eq. ( 1), or equivalently on finding an accurate approximation for the probability P t . The latter expresses the probability to find a path at time t (no longer than D edges) between a generic couple of vertice (n it+1 , n jt+1 ), knowing that the number of already existing edges is l t .

To fulfill this objective, we first leverage a well known property of the matrix A t : A c t (i, j) = 0, c ∈ N + , if and only if no path composed of c edges exist between n i and n j at time t [START_REF] Noel | Understanding complex network attack graphs through clustered adjacency matrices[END_REF].

In this way, without lack of generality, P t can be expressed as follows:

P t = D ∏ c=1 P r{A c t (i t+1 , j t+1 ) = 0} (4)
Now, given that 2 • l t elements are equal to one in A t , it yields P r{A t (i, j) = 1} = 2•lt N 2 . Also, since any element of A c t is no other than the sum of N c-1 elements, each one being a product of c coefficients belonging to A t , we can approximately write:

P r{A c t (i t+1 , j t+1 ) = 0} ≈ [ 1 - ( 2 • l t N 2 ) c ] N c-1 (5)
Now, recalling that (1 + 1 x )

x → e, when x → ∞, for a sufficiently large N , Eq. ( 5) can be written as:

P r{A c t (i t+1 , j t+1 ) = 0} ≈ exp ( -N c-1 • ( 2 • l t N 2 ) c ) (6)
Accordingly, by substituting ( 6) in (4), it is obtained:

P t ≈ exp ( - D ∑ c=1 N c-1 • ( 2 • l t N 2 ) c ) (7)
which, after a little algebra, becomes

P t ≈ exp ( - 1 N • ( 2•lt N ) D+1 -2•lt N 2•lt N -1 ) (8)
From [START_REF] Erdos | On the evolution of random graphs[END_REF], the average degree can be expressed as k t = 2•lt N , so that we obtain the proof by substituting ( 8) in [START_REF] Babaei | Cascading failure tolerance of modular small-world networks[END_REF].

III. NUMERICAL VALIDATION

To validate the model (3), we have considered a complex scenario composed of N vertice (with N ranging from 2 5 to 2 16 ) and D ranging from 3 to 10. Using an ad hoc simulator we developed in Matlab, the relative error between the real evolution of the degree k(t) and the one estimated using (3) for all t is evaluated. In any case, we found that the average relative error is below 10% if we consider the entire evolution of k(t). Also, the relative error at steady state (once the graph is completely formed), for D ≤ 5, is below 10%, whatever N . Finally, we notice a slight increase in the relative error as D increases: (in any case) it remains smaller than 25% and it falls below 20% for N > 2 12 .

To provide an illustrative example, Fig. 2 plots the dynamic evolution of the number of edges versus the time t (similar results have been obtained for different values of N and D so that the average relative error is below 10% in all cases). It is worth to note that the number of edges linearly increases with t till a saturation point is reached. From that moment on, l exhibits a very slow rise. This can be explained by plotting also the values of the probability P t . Fig. 3 shows that P t is almost equal to one for some time during the network formation, meaning that, since the number of edges is low, it is highly likely to add a new edge as soon as a new couple of nodes needs to establish a path. At the same time, the values To provide a further insight, Fig. 4 pictures the evolution of a random graph (N = 1000, D = 5): (a) at the beginning of the simulation, when no edge is present; (b) during the transient, when a few edges have been created and a new edge is added; and (c) at steady state, when all required paths (no longer than D edges) have been already created.

IV. EXAMPLE APPLICATIONS

A. Rank bound and convergence

Theorem 1. Being k the maximum degree k in system [START_REF] Chen | Synchronization of complex networks with impulsive control and disconnected topology[END_REF], it can be bounded as follows: Proof. The way we are building the overlay is so that an edge between a couple of vertice (n it , n jt ) is formed or not based only upon the first time that couple issues a request for a path. If a path shorter than D + 1 hops already exists the edge is not established otherwise it is established. From that moment on, the next requests for a path issued by the same couple of vertice will not sort any effect.

k ≤ D √ 2 • N • lnN . ( 9)
Based on this consideration, we extract from the sequence of equi-probable couples of vertice considered in the brief, the sequence of instants in which any couple of vertice appears for the first time. Of course, the length of such a sequence of time instants will be composed of at most N (N -1)/2 elements.

In order to estimate an upper bound on the steady state average degree k, it is necessary to consider that at time t, 1/P t expresses the average time required to establish the next edge in the overlay.

Under this assumption, the expression of P t to consider is slightly different from that in Eq. ( 8) because the sequence of vertix couples we are considering to proof this Theorem is chosen in such a way that no one edge path exists at time t for (n it , n jt ). The avoid ambiguity, we will refer to P ′ t to refer to this new probability. Accordingly, it follows:

P ′ t = D ∏ c=2 P r{A c t (i t+1 , j t+1 ) = 0} (10)
which, following the same passages reported in the proof of Proposition 1, can be also written as:

P ′ t ≈ exp ( - 1 N • ( 2•lt N ) D+1 -( 2•lt N ) 2 2•lt N -1 ) (11)
Therefore to estimate an approximated upper bound on k, it is sufficient to find any value of k t so that 1

P ′ t ≥ N (N -1)/2, which gives ∑ c=2 D k c t ≥ 2 • N • lnN -N • ln2. Notice that the latter inequality is satisfied if k D t ≥ 2 • N • lnN , from which the proof follows.
Remark 1. It is worth remarking that, the bound k can be fruitfully exploited to compare the properties of the graph under study with respect to well known graph. To this end, if we consider as ground for comparison the delay optimal de Bruijn graphs, representing one of the most compact topologies discovered so far [START_REF] Loguinov | Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience[END_REF], we will find that, for the same diameter D, the degree of the unstructured overlay considered in this brief is only D √ 2 • lnN times larger at most, even if it is based on a much simpler construction mechanism.

B. Robustness

Knowing that the graph construction model adopted herein ensures, at steady state, at least one path shorter than D + 1 edges between any couple of nodes, it is worth investigating how many paths (composed of less than D + 1 edges) are present between any couple of nodes. This metric is intimately related to the topology robustness: the higher the number of paths the higher the number of alternative solutions to route messages in case of failures. Theorem 2. Defined as w t the number of paths composed of less than D + 1 edges between any couple of nodes at time t, it holds:

w t = 1 N • k D+1 t -k t k t -1 (12)
Proof. Also in this case the properties of the adjacency matrix are exploited. In particular, A c t (i, j) indicates the number of paths composed of c edges between the vertice n i and n j . Thus, considering that the average value of any element if A is 2•lt N 2 , it holds:

w t = 1 N • D ∑ s=1 k s t = 1 N • k D+1 t -k t k t -1 (13)
This end the proof.

Based of this Theorem, we can derive an approximate assessment of the level of redundancy, if we consider for k t , the bound derived in Theorem 2, i.e., k t = D √ 2 • N • lnN . Under this assumption, we can obtain:

ŵ = 1 N • (2 • N • lnN ) D+1 D -2 • N • lnN 2 • N • lnN -1 > 2 • lnN (14)
This result indicates that the overlay investigated in this brief is able to provide at steady state at least two paths among any couple of vertice, for N > e.

C. Link failures

To include also possible link failures and dynamics in the model, it is necessary to modify Eq. (1) as follows:

l t+1 = l t + P t -λ o • l t ( 15
)
where λ o is the probability that an edge is removed during one time step. The resulting equations could be very useful to design topology management algorithms using control theoretic arguments. Its utility in finding the uniquness of the equilibrium point is shown in the following Theorem.

Theorem 3. The system [START_REF] Alaya | Autonomic computing system for self-management of machine-to-machine networks[END_REF] admits one and only one equilibrium point l = l ∞ .

Proof. In order to find the equilibrium point of system (15), we impose l t+1 = l t = l ∞ in [START_REF] Alaya | Autonomic computing system for self-management of machine-to-machine networks[END_REF]. Accordingly, the following equality is obtained:

P ∞ = λ o • l ∞ ( 16
)
Eq. ( 16) admits only one solution because its leftmost member monotonically decreases with l, starting from the value one at l = 0 whereas the rightmost member monotonically increases, starting from zero at l = 0.

This ends the proof.

V. CONCLUSION

A novel tractable model for describing the dynamics of a diameter constrained random graph is proposed, validated, and analyzed in this brief. Useful examples of its adoption have been also provided in order to demonstrate its real utility. Future research will encompass: (i) the evaluation of gravity based features and heterogeneous conditions; (ii) the characterization of M2M overlays; (iii) the study of the properties of the equilibrium point found in Theorem 3; and (iv) the formulation of a control theoretic framework for overlay topologies built upon the model proposed herein.

Fig. 1 .

 1 Fig. 1. Evolution of a random graph (N = 5, D = 2): a) initial state; b)the first edge is added at t = 1 to connect vertice n 2 and n 4 ; c) the second edge is added at t = 2 to connect vertice n 1 and n 4 , but no edge is added at t = 3 because the vertice n 1 and n 2 (asking for a connection) are already connected by a path of 2 hops ≤ D; d) the third edge is added at t = 4 to connect vertice n 4 and n 5 ; e) the fourth edge is added at t = 5 to connect vertice n 2 and n 3 ; e) the fifth edge is added at t = 6 to connect vertice n 1 and n 3 , for which the only existing path was longer than D hops.

Fig. 2 .

 2 Fig. 2. Evolution of the number of edges over the time t, (N = 1000, D = 5).

Fig. 3 .

 3 Fig. 3. Evolution of Pt, (N = 1000, D = 5).

Fig. 4 .

 4 Fig. 4. Evolution of a random graph (N = 1000, D = 5): a) initial state; b) during the transient a new edge is added; c) at steady state no edge is added because paths no longer than D hops already exist.

It is worth to note that equi-probable arrivals (i.e., homogeneous conditions) are usually assumed in the current literature dealing with diameter constrained graphs[START_REF] Loguinov | Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience[END_REF]. In fact, if the vertice of the graph represent the gateway through which the service of a large number of nodes are made available (as in M2M systems[START_REF] Dhraief | Autonomic management of the HIP-based M2M overlay network[END_REF]), it is not unlikely that the overlay that inter-connect such gateways actually reflects this assumption.

ACKNOWLEDGMENTS

This work was supported by the INSA of Toulouse (FR).