André Moliton
email: amoliton@unilim.fr

Bruno Lucas

Sébastien Berthon

Wassim Rammal

Roger C Hiorns

Transport mechanisms in 8-tris-hydroxyquinoline aluminium (Alq3) electronic layers: a study by photodipolar absorption

This paper describes the role of traps in the electronic conductivity of 8-tris-hydroxyquinoline aluminium in a conventional sandwich structure with indium tin oxide and aluminium electrodes. New results obtained by photodipolar absorption techniques and impedance spectroscopy are presented. The former method acts as a probe to highlight the role of traps.

It is shown that optical pumping of electrons to trap levels gives a clear increase in dielectric absorption due to the reorientation of dipoles associated with trapped charges. The trap depth is estimated to be around E t = 0.19 eV, a value in good agreement with theoretical calculations and thermoluminescence measurements.

The latter method permits a representation of the sample in terms of a circuit composed of a parallel capacitor (C p ) and resistor (R p ) both in series with a resistor R s ≈ 50 located on the anode side. A logarithmic plot of R p as a function of the dc bias voltage gives a linear law that is recognized, for the first time, to be a consequence of a trapped charge limited (TCL) current. The linearity can be improved by the introduction of a field-dependent mobility.

In the development of molecular materials for organic optoelectronics, particularly for applications using electroluminescence, the electron emitter 8-tris-hydroxyquinoline aluminium (Alq3) has been studied in depth [START_REF] Forsythe | paper presented at the SPIE conference[END_REF]. Figure 1 shows the chemical structure of this material which is an organometallic complex based on a central metal cation coordinated to quinolate ligands. It is generally prepared as a thin film by evaporation under vacuum, which in itself demands that the complexes exhibit no overall charge or saturated coordination numbers [START_REF] Miyata | Organic electroluminescent materials and devices[END_REF]. Alq3 satisfies these requirements and is the most widely used compound, even if its fluorescent quantum yield is relatively low. It provides films with a stable electroluminescence and is a good transporter of electrons.

[Insert Figure 1 about here please] Numerous discussions have taken place concerning the electronic conduction mechanisms and the role of traps in Alq3 [START_REF] Ioannidis | [END_REF]. For example, a trapped charge limited (TCL) model in which the trapping time is longer than the average transit time for a hop between the LUMOs of two molecules, was proposed to answer criticisms concerning electronic transport in a band structure where there is a sufficient delocalization of carriers to establish a thermal equilibrium between free and trapped charges [4].

In this paper, we present new results, which, on interpretation, advocate the use of conductivity laws involving trap mechanisms. Experimental results are based on photodipolar absorption measurements obtained from thermo-photo-dielectric effects, as currently used with inorganic materials (class II-VI semiconductors such as ZnS(Cu)). This technique has not been used before with Alq3 to our knowledge, and is here complemented by the use of impedance spectroscopy. We discuss the possibility of a modified TCL law to take into account a dependence of the mobility on applied electrical field.

2 Electronic structure and transport mechanisms in an indium tin oxide/Alq3/Ca(Al) sandwich device

Energy levels in Alq3

In polymers each monomer is joined to its neighbours by strong bonds, which have associated with them transfer integrals β [5]. However, in thin films composed of molecules, cohesion arises from weak Van der Waals forces between weakly overlapping orbitals of the molecules. In addition, the greater the distances between the molecules, the weaker the interactions between electrons on neighbouring molecules and the lower the degeneracy of valence states. As the discrete occupied levels increase with increasing numbers of chemical groups, the separation, or band gap, between HOMO and LUMO bands decreases [START_REF] Pope | Electronic processes in organic crystals[END_REF], as is the case for polymers. The result is that the electronic bands obtained for molecular solids are narrow and exhibit poor interaction. It should be noted that the term 'band' here corresponds simply to an energy interval in which HOMO and LUMO levels are situated, without implying a Bloch pseudo-continuum of energy levels.

As shown in Figure 2, Alq3 is a large molecule consisting of a central metal cation tied to 3 surrounding ligands, and the interactions between ligands must not be ignored. A study has been made using semi-empirical determinations of molecular orbitals to compensate for this intermediate neglect of the differential overlapping (INDO) method [START_REF] Rivail | Eléments de chimie quantique[END_REF]. By considering an isolated molecule of Alq3 and assuming that it exhibits the same characteristics as a molecule within a thin film (i.e. simply ignoring the effects of the weak Van der Waals forces between molecules), energy levels were determined by Burrows et al. [4]. The calculations indicated that full π-orbitals (HOMO) are situated at the ligand phenoxide groups while empty π*-orbitals (LUMO) reside around ligand pyridine groups.

[Insert Figure 2 about here please] Figure 3 shows absorption and electroluminescence spectra of Alq3. The electroluminescence peak is red shifted by ≈ 0.4 eV from the absorption peak. This is a

Franck-Coulomb shift results from large conformational changes on optical excitation. These conformational changes, arising from strong electron-phonon coupling, broaden the electroluminescence spectrum and give rise to discrete trapping levels in the HOMO-LUMO gap.

[Insert Figure 3 about here please]

Interface barriers

The work functions of indium tin oxide (ITO), calcium and Alq3 are denoted by W ITO , W Ca and W Alq3 , and the electron affinity, the ionization energy and the size of the forbidden band of Alq3 by χ Alq3 , I PAlq3 and E GAlq3 , respectively. Experimental values are W ITO = 4. = 2.9 eV, χ Alq3 = 3.3 eV, E GAlq3 = 2.6 eV, so that I PAlq3 =χ Alq3 + E GAlq3 = 5.9 eV (values for Alq3 were obtained from Schmidt et al. [START_REF] Schmidt | [END_REF]).

Organic light-emitting diodes (OLED)s are generally fabricated as detailed in Figure 4 (a) [START_REF] Moliton | Optoélectronique moléculaire et polymère : des concepts aux composant[END_REF]. Once contact is made with the electrodes, the bands move through the adjustment of Fermi levels such that V FB = (W ITO -W Ca )/q where V FB is the voltage difference of the flatbands and V app is the applied dc bias voltage (Figure 4(b)). The drop in voltage that appears of its own accord is in fact what we term V PS (the 'positive supplementary' voltage applied to the ITO anode), and is equal to the total applied voltage minus the flat-band voltage (V FB ). In this example V FB ≈ 2 V, a non-negligible value with respect to those generally used (of the order of 0 to 15 V).

Important information can be gained about the interfaces. The barrier at the anode ( A ), observed by holes, is equal to A = I PAlq3 -W ITO . In this example A = 1.3 eV. It is more than probable that the contact at the anode is not ohmic and risks being limited by emissions from the anode. At the cathode there is no barrier to the injection of electrons. The drop in potential energy for electrons C = χ Alq3 -W Ca ,which gives C = 0.4 eV. This contact can be assumed to be ohmic because near the electrode the Fermi level penetrates the Alq3 LUMO.

[Insert Figure 4 about here please]

Transport mechanisms

Introduction

Various mechanisms can be envisaged for charge transport. The voltage and current flow characteristics of a material are usually studied and explained in terms of charge injection under an electric field (Schottky effect) or by tunnelling, in which case the current is electrode-limited. However, as here, the results may be interpreted using models based on current flow through the bulk of the material. It is important to note though that in order to reduce the threshold potential of the device (ITO/Alq 3 /Ca(Al)), the effect of the metal used for the electrode or the mobility of carriers within the organic layer should be characterized depending on the technique used.

Studies of I(V) characteristics have shown that Schottky emissions can give an ideality

factor n of the order of 20 (a very high value indeed) and an unusually high diode series resistance of 50 k . However, the emission law for tunnelling effects (Fowler-Nordheim law) is not completely verified [4,[START_REF] Antony | [END_REF]. In fact, it is the Alq3 bulk that limits the current flow and furthermore, the conductivity cannot arise from carriers in extended states. In fact, the I(V) characteristic follows the TCL relation I ∝ V m+1 /d 2m+1 , notably within domains that yield electroluminescence.

Conduction processes and trapping levels

Qualitatively, in Alq3, the Al 3+ ion complexes with the 3 ligands to leave them with the capability, through back bonding, to act as effective electron acceptors. This character results in the easy propagation of electrons between molecules. The material is therefore considered to be n-type.

The existence of extended states in condensed small molecules is controversial. As mentioned above, semi-empirical calculations have been used to determine the energy levels for an isolated molecule. However, the weak Van der Waals intermolecular interactions do not even yield narrow molecular bands. When dealing with electroluminescence, the continuity (or non-continuity) of energy levels susceptible to receiving injected charge carriers at interfaces is problematic. If the energy separation between levels is too great, then there is a risk that any injected charge will not find an accepting energy level. Given the size of the molecule however, it is probable that there is a large number of energy levels and consequently these should be sufficiently close to ensure that charge carriers are not blocked.

Even if there are permitted bands arising from weak Van der Waals bonding, the very limited overlapping of molecular orbitals makes these bands narrows (B < kT) and the effective-mass approximation can no longer be applied to evaluate charge mobility.

By assuming that any collision is isotropic, and therefore that the relaxation time is equivalent to the time between two consecutive collisions, a general equation for the mobility µ [START_REF] Wright | Molecular crystals[END_REF] leads-with the Ioffe and Regel rule l > a (where a represents an average intermolecular distance and l the mean free pathway of an electron) [START_REF] Ioffe | Non crystalline, amorphous and liquid electronic semiconductors[END_REF]-to the inequality µ > qa 2 / ћ [START_REF] Moliton | Optoélectronique moléculaire et polymère : des concepts aux composant[END_REF]. Given that a ≈ 5 x 10 -8 cm, we find that µ ≥ 1 to 10 cm² V -1 s -1 . With µ << 1 cm² V -1 s -1 (µ ≈ 5 x 10 -5 cm² V -1 s -1 in Alq3), we do not have the inequality required (i.e. µ ≥ 1 to 10 cm² V -1 s -1 ) to obtain conduction through delocalized states.

Structural defects resulting from electron injection into Alq3 have been studied.

According to Section 2.1, an injected electron should enter the first empty level localized around pyridine groups. In order to determine the approximate trapping energy associated with an electron injected into Alq3, calculations were performed for a neutral Alq3 with the geometric structure of its anion [START_REF] Forrest | Organic electroluminescent materials and devices[END_REF]. Transition energies of 3.07 to 3.20 eV and 3.34 eV underwent a large red shift of the order of 0.21 eV with respect to the neutral and fundamental . This relaxation towards a lower energy level can be used to automatically trap an electron that would otherwise move to a neighbouring molecule through polaronic processes. Given that there are many possible variants to the Alq3 structure, an exponential breakdown of trap levels leading to distribution of levels in the LUMO band is possible. The upshot of this is that conduction mechanisms associated with trap levels can therefore appear in otherwise resistive media.

In the next section, we briefly recall the main results for current flow obtained with electrical conduction involving traps. For the discussion section, a clear understanding of the mechanisms leading to the physical laws is of importance.

Transport mechanisms in resistive organic materials with traps; effective mobility

2.3.3a The space-charge-limited-current law without traps

The current can be space-charge limited when the contact is ohmic. Given that the Alq3 is close to being an insulator, space-charge formation near the electrode interface opposes the trickle of current through the material. At a sufficiently high applied field (E a ), the space charge is pressed right back to the interface and can effectively enforce a saturation current.

At this point, it is important to recall the hypotheses leading to the common space-chargelimited (SCL) law. First, the band model is applicable to the treatment of injection of carriers with a current not limited by the electrode. While considerable controversy does surround the question of whether or not band models can be applied to organic solids, a model does indeed exist for these [5,[START_REF] Pflüger | Handbook of conducting polymers[END_REF], which is close to that proposed for amorphous semiconductors [START_REF] Mott | Electronic processes in non-crystalline materials[END_REF].

The most important assumption of the model is that the energy levels within an insulator, localized or not, can accept injected charges at the interface. Second, carrier mobilities are assumed to be independent of E a and the dielectric permittivity (ε) is not modified by charge injection. Poole-Frenkel or impact ionization effects are not considered. Third, the electric field is assumed to be high enough to render negligible the following current components:

-ohmic current due to thermally generated carriers with density n 0 as under a high injection regime n >> n 0 ;

-current due to diffusion, because the applied potential is considerably greater than the thermal potential kT/q. Fourth, the system is essentially one-dimensional when E a is sufficiently intense for the resulting field at the cathode to be equal to zero. If J s is the saturation current, given the above conditions [START_REF] Kao | Electrical transport in solids[END_REF], it is possible to state that 2 2 a a 3 9 9 8 8

s V E J d d ε ε = = .

2.3.3b The effect of traps: the effective mobility and the modified SCL law

If n is the density of free charges with mobility µ n , and n t the density of trapped charges on a discrete level E t , then the current density (J) can be written either as J = q n µ n E a or as J = q

(n + n t ) µ eff E a which defines the effective mobility (µ eff ). The current density with traps (J sT )

becomes

J sT = 2 a eff 3 9 8 V d ε = 2 a eff 9 8 E d ε .
Traps can be distributed according to a Gaussian law. Accordingly, the density of traps per unit energy (g(E)), centred about energy E, is of the form

g(E) = (N t /kT t )exp(-[E c -E]/kT t )
in which N t is the total density of trap levels and T t is a constant characteristic of the distribution. Taking T t =E t /k = mT in which E t represents the characteristic energy of traps with respect to E C and m a characteristic of the trap distribution, the current density is generally TCL and given by

J ≡ J TCL ∝ V m+1 /d 2m+1 .
Qualitatively, an ohmic law is followed at low voltages (due to thermally generated carriers of density n) in thick films. As the voltage increases, the Fermi pseudo-level rises and traps start to fill. This decrease in the number of empty traps, which can now receive few electrons, induces a rapid increase in the mobility and the overall current, resulting in the TCL law being observed (I ∝ V m+1 /d 2m+1 ). At a sufficiently high value of V, all traps are filled and the classic SCL law may be observed. However, such values for V are rarely obtained without destroying the films.

Numerous arguments have been developed as to why the TCL law is observed [4] but controversial points have been raised [START_REF] Ioannidis | [END_REF], as will now be discussed. Apart from doubts concerning the validity of the band scheme for small molecules, another controversial point relates to the hypothesis of the invariance of carrier mobility with respect to an electric field, which is used in establishing the SCl and TCL laws. Because of the low mobilities and short mean free paths in organic solids, Kao and Hwang proposed that, between successive collisions, the carriers could not gain much energy from an applied field, and hence their mobilities should be essentially independent of the applied field [START_REF] Kao | Electrical transport in solids[END_REF].

Controversial points

However, in disordered systems, general expressions for µ are obtained empirically and have only been verified through Monte Carlo simulations [START_REF] Bässler | [END_REF], or in accordance with an empirical law for charge transfer [18]. Carriers in small molecules generally exhibit a mobility which follows the Poole-Frenkel law in the form µ ∝ µ 0 exp(αE a 1/2 ). However, in certain materials, such as polymers doped with molecules to the order of 5 to 25 % by mass, mobilities do decrease above a certain value of E a . As shown in Figure 5, in qualitative terms, we can suppose that this effect is due to 'diagonal disorder' associated with the variable distances between molecules [START_REF] Greenham | Semiconductor Device Physics of Conjugated Polymers[END_REF]. Under a weak field, there are many available and facile pathways (short distance hops in different directions with respect to the field) which are, nevertheless, removed once a strong field is applied.

[Insert Figure 5 about here please]

Alternative models

By modelling the characteristics of organic materials such as Alq3, Ioannidis et al. showed that trapping levels need not be invoked [START_REF] Ioannidis | [END_REF]. This group even supposed that such levels do not exist, because in examples where only electrons have been injected (using the same contacts on either side, which are assumed to be ohmic), the I(V) curves are identical whether or not the applied voltage is interrupted during the measurements, indicating negligible electron trapping. They consider that experimental characteristics may be based on Ohm's law, into which can be included an appropriate law for a variation in mobility of the form µ = µ 0 exp(αE a 1/2 ) where µ 0 is the mobility under a weak field and α a parameter increasing with disorder. In their fitting, they found α = 1.3 x 10 -2 cm 0.5 V -0.5 and µ 0 = 6.5 x 10 -10 cm² V -1 s -1 .

It is important to state, however, that the presence of trapping levels has been confirmed using a variety of techniques. These include thermo-stimulated luminescence (TSL) spectroscopy which was demonstrated by Forsythe et al. [START_REF] Forsythe | paper presented at the SPIE conference[END_REF] in the modelling of a principal peak using a distribution of traps with energies between 0.25 and 0.15 eV (two In order to demonstrate the presence and calculate the depth of trapping levels in Alq3, we undertook a study by photodipolar absorption as detailed in the following section.

Experimental: photodipolar absorption and impedance spectroscopy

The photodipolar effect consists of three major components, which are: a photonic effect from the pumping of electrons to the trap level-or to the conduction band-with a subsequent release from traps; a thermal effect associated with the initial cooling of the sample; and a dielectric effect arising from the relaxation of dipoles produced by the polarization of trapped electrons. The energy of the trapping levels is the activation energy that can be determined from dielectric absorption measurements as a function of frequency and temperature.

Experimental procedures

Alq3, obtained from Aldrich, France, was deposited by thermal evaporation onto an ITO (ca 300 nm thick on a glass substrate and obtained from Merck, France) plate in a secondary vacuum (ca 10 -6 mbar), and then covered with aluminium (ca 100 nm thick layer) by thermal deposition. Once the sample cell was prepared, with electrical contacts placed on opposite sides of the sample in order to prevent short-circuits as shown in Figure 6, it was transferred to the apparatus schematized in the various electrical currents in the sample, in order to determine the true dielectric response of Alq3 the other components that are concurrently measured must also be determined [START_REF] Jonscher | Dielectric relaxation in solids[END_REF].

In other words, effects due to the true dielectric loss, characterized by the imaginary component of the dielectric susceptibility (χ"), must be separated from those due to: the dc conduction (σ 0 ) caused by free charges that are practically independent of frequency (at least in the low-frequency range); hopping conduction (σ h ); photoconduction (σ ph ) for an illuminated sample; and variations at the interfaces between Alq3 and the electrodes. For the measured apparent dielectric loss, or rather the imaginary component of the effective dielectric response (ε") it is therefore possible to write 0 '' ''

σ ε χ ε ω = +
where σ = σ 0 + σ h + σ ph . Following from the discussion above, the last component (σ /ε 0 ω) arises only because the instrument cannot distinguish between true dielectric and electronic transport processes. In the Debye model, the dielectric loss due to χ" can be represented as a double potential well as schematized in Figure 8. Under the influence of an applied alternative electric field, the electrons oscillate around an equilibrium position between positions A and B, which are separated by a potential barrier of height U. In the most simple scenario, the mechanism for the oscillation is a relaxation process of time constant τ where ( )

0 exp / U kT τ τ = .
When the dielectric loss is at a maximum, = 1 c ω τ

, and the activation energy U can be related to the trap depth by U = E t , as has been possible for luminescent inorganic II-VI semiconductors. It is possible to distinguish the component σ 0 from dielectric phenomena because ε"(ω) is proportional to 1/ω and, on decreasing ω towards 0 Hz when ε'(ω) attains a constant value, the remaining measurement is due to σ 0 which becomes the dominant process. The component σ h has often been observed in amorphous materials and various theories have been proposed to define it. The most widely used is σ h = C ω s , where s = s(T) in accurate theories [START_REF] Mott | Electronic processes in non-crystalline materials[END_REF]. However, for amorphous materials with traps, the photoconductivity may be discerned as a function of temperature through the equation where τ T is the time required for electrons to recombine with traps, G is the rate of generation of photocarriers, N c is the density of states in the conduction band, and N t is the density of trap levels [START_REF] Morigaki | Physics of amorphous semiconductors[END_REF]. The effects due to the contacts between the Alq3 and the electrodes cannot be neglected, especially when considering that the film is relatively thin. Equivalent circuits, generally consisting of a parallel resistor (R p ) and capacitor (C p ) in series with a resistor (R s ), that exhibit a virtually temperature-independent absorption peak in the relevant frequency range may be used [START_REF] Jonscher | Dielectric relaxation in solids[END_REF].

( / ) exp(-[ -]/ ) ph T c t c t q G N N E E kT
[Insert Figure 8 about here please]

Results from dielectric experiments

During illumination, excited electrons are 'pumped' from the HOMO to the trap levels, with a transient photo-electronic process around the LUMO levels as schematized in Figure 8. The results from the dielectric analyses of the sample are presented in Figure 9 (curves 1-4).

Without illumination and under relatively fast heating, the sample gave a small and near constant response (curve 1). Again without illumination, but with slow heating, the dielectric response was weak with a broad peak at around 220 K caused by trapped electrons excited by ambient natural light (curve 2). Under illumination during both the cooling and heating passages, a component due to σ h , which eclipsed the dielectric contribution could be observed (curve 3). With illumination during only the initial cooling passage, the dielectric response could be clearly discerned at around 220 K on the heating passage (curve 4). It should be noted that as fluorescence is a near-instantaneous process with a relaxation time of less than 1 ms, it would not have interfered with the data in curve 4 on account of the delay of several minutes between the illumination during the cooling passage and the measurement during the heating passage.

[Insert Figure 9 about here please] E t ≈ 0.19 eV. This value is in good agreement with that obtained elsewhere by thermoluminescence studies (0.15 eV <E t < 0.25 eV) [START_REF] Forsythe | paper presented at the SPIE conference[END_REF], TCL measurements (E t = 0.15 eV) or theoretical calculations (E t = 0.21 eV) [4]. From Figure 11(b), derived from the (b) plots of Figure 10, it was possible to conclude that electrons are trapped for a considerable time (several minutes) at the low temperatures used in this study; the level of the traps (E t ) was calculated to be 0.18 eV, and it is probable that they are nearly identical in nature to those filled by the action of the lamp light. It should be noted that to obtain reproducible curves, slow heating passages (ca 0.5 °C min -1 ) were required.

[Insert Figures 10 and 11 about here please]

It is interesting to note that in going from 100 Hz to 1 kHz there is a steady increase in the intensity of the Debye peaks shown in Figure 10. This increase is most probably due to a superposition of two effects. Firstly, the thermally activated process of photoconductivity, as detailed in Section 3.2, which gives rise to a large increase in conductivity at the higher temperatures indicated in Figure 9 (curve 3). Secondly, even if the excitation caused by UV is suppressed, as indicated in curve 3 and to a lesser extent in curve 2 where excitation is caused only by natural light, the photodipolar measurements can be influenced by a slow process of phosphorescence, which may be of non-negligible intensity for a period of several tens of minutes. The combination of the weak photoconductivity (without peaks) and the Debye absorption (that generates peaks) results in this behaviour; so, as the actual positions for the peaks remains unchanged in relation to a classical Debye behaviour, the calculated activation energies are nevertheless directly related to the photodipolar absorptions and therefore also the trap depths.

Study of the contact resistance by impedance spectroscopy

In order to calculate the contact resistance in the ITO/Alq3/Al device, impedance spectroscopy was used. Figure 12 shows a Cole-Cole plot at several dc bias voltages. The minimum value for Re(Z), obtained at the highest frequency, indicates that R s has a value of ca 50 . The maximum value for Re(Z), obtained at the lowest frequency, indicates the sum of R s and R p , and therefore R p can be calculated to be ca 1. around 50 and 15 respectively, it is possible to think that R s is located at the anode side of the equivalent circuit. Importantly, the analysis made above also indicated that the interface capacitance was negligible, and the interfaces could therefore be assumed to have no air gaps or insulating barriers.

[Insert Figure 12 about here please]

Discussion on possible improvements to the TCL law

As traps have been shown to exist through photodipolar effects, it is useful to consider the accuracy of the TCL law and, indeed, how it may be improved. As shown in Figure 13, R p decreases as the dc voltage increases while C p (= 1/ω max R p ) is almost independent of the dc bias voltage. This observation was also made for a similar device based on PPV instead of Alq3 [START_REF] Kim | [END_REF]. From the TCL law given by

J = K +1 2 +1 m m V d
, where K is a constant, it is possible to deduce the voltage dependence of the resistance R p in such a way that

-m p R V J V ∝ ∝ . On
plotting log R p against log V, as in Figure 13, it was found that m ≈ 2.5. On making a first analysis, the reasonable linearity of the R p versus log V plot would seem to indicate that the conductance followed the TCL law owing to an exponential trap distribution. However, on further inspection, it can be noticed that the plots in Figure 13 do not follow perfectly straight lines. Indeed, plots of log J against log V elsewhere in the literature are also not linear [START_REF] Antony | [END_REF]. It should also be noted that the latter results did not exhibit the Fohler-Nordheim law, which would indicate that the conductivity was bulk limited. Therefore, there is every possibility that an improvement can be made to the TCL law. By taking into account the dependence of mobility on temperature and electric field, it seems reasonable that effects due to space charges and the applied electric field should affect J(V) characteristics [START_REF] Shen | paper presented at the SPIE conference[END_REF].

[Insert Figure 13 14 by trapped charges, as here, then, with traps distributed according to an exponential energy curve, m = T c /T for which E t = kT c . While J ∝ V m+1 , the J(V) law follows variations in µ. As the latter is not a constant, then J will no longer follow a law based on V m+1 .

The problem therefore is to resolve whether space charge or mobility is dominant in any specific voltage domain. If it can be supposed that mobility varies slowly enough with respect to E a , so that an integration of Laplace's equation may be performed (Section 2.3.3 (a,b)), the appropriate law for the mobility, i.e. µ(E a ,T), may be introduced into the TCL equation. If, however, the mobility varies strongly with respect to E a , the integration of Laplace's equation becomes problematic. While attempts to obtain a field-dependent mobility from space-charge-limited-current variations against voltage have been presented

elsewhere [START_REF] Natali | [END_REF], the complexity of such equations make direct numerical treatment impossible, negating any contribution to the hypothesis of conduction by traps.

Conclusions

The presented experimental results and a consideration of the electronic structure of Aq3 have indicated that the conduction mechanism in a device based on ITO/Alq3/Al is bulk limited.

The TCL law would initially seem the most appropriate to describe electron transport in the device; however, improvements could be made to this law by bringing in a term to describe field-dependent mobility. Photodipolar absorption measurements indicated by a dielectric effect the presence of traps with depths of around E t = 0.2 eV. Optical pumping of electrons to trap levels gave a clear increase in the dielectric absorption. This method may therefore be used effectively to probe traps and demonstrates that the once controversial hypothesis that traps are present in Alq3 has been affirmed.

(2)

(1) (1)

  , a value which represents the electron trap energy depth. It was also thought that these calculations provided insight into the nature of the traps in Alq3. When an additional electron is localized on a molecule it occupies anti-bonding orbitals and the molecule accordingly relaxes into a new structure (Frank-Condon principle)

  observed at lower energies), and the characterisation of thermostimulated currents (TSC) as performed by Meier et al.[START_REF] Meier | [END_REF] and Nguyen et al.[START_REF] Nguyen | Handbook of Advanced Electronic and Photonic Materials and Devices[END_REF] on polymers such as poly(phenylene vinylene) (PPV).

Figure 7 . 3 . 2

 732 The experimental measurements were performed using a Hewlett-Packard 4274A bridge. Samples were cooled to 77 K and then data were obtained in the 20 Hz -1 MHz frequency range during heating passages from 150 K to 320 K. A Wood lamp, Model B 100 AP UVP manufactured by Upland, USA, and supplied by Fisher Bioblock Scientific, France was used to supply the UV illumination at an intensity of 7000 µW cm -2 and a wavelength (λ) of 365 nm (figures supplied by the manufacturer in accordance with the filter used on the lamp). The sample was also exposed to ambient natural light.[Insert Figures6 and 7about here please] Components observed by dielectric absorption spectroscopy the results from the dielectric experiments, it is worth discussing what has actually been measured. Since the dielectric absorption analyses cannot discriminate between

Figure 10 shows

 10 Figure 10 shows curves for ε" = f(T) at a range of frequencies for the samples exposed to the lamp light or only natural light during the cooling curve, respectively denoted (a) and (b). The dielectric peaks are at higher temperatures as the frequency increases, a characteristic of Debye dielectric absorption. The curve of log ν c = f(1/T) shown in Figure 11(a) and derived from the (a) plots in Figure 10 permits a calculation of the activation energy

7 x 10 3

 3 at zero dc bias. Given that experiments performed on similar devices made from ITO/Alq3/Au (in which the work functions of ITO and Au are of the same order) and Al/Alq3/Al indicated a value for R s of

  about here please] On reconsidering the general expression for current density, and ignoring the term for diffusion, J = ρv =qnµE, where n is limited by space charge. The equation may be rewritten in the form J = qnµV/d, and n is generally proportional to V m , where m = 1 when only free untrapped charges contribute to the space charge. This in effect gives rise to the saturation current (J s ) as indicated in the Mott-Gurney law. However, if the space charge is dominated

  Figure CaptionsFigure 1.Chemical structure of Alq3.

Figure 2 .

 2 Figure 2.Localization of full (HOMO) and empty (LUMO) orbitals on Alq3.

Figure 3 .

 3 Figure 3.Absorption and electroluminescence spectra of Alq3.

Figure 4 .

 4 Figure 4. (a) Typical set up for an OLED based on ITO/Alq 3/Ca in which the ITO layer is about 300 nm thick, the Alq3 film is around 75 nm, the calcium is approximately 250 nm and the aluminium electrode is ca 75 nm; and (b): the associated band scheme.

Figure 5 .

 5 Figure 5.Qualitative description of charge transport under strong and weak fields.With a strong field, collisions are orientated and electrons are forced to follow a certain trajectory. On meeting a barrier, their passage is arrested, and thus mobility decreases when E a is very high. With a weak field, however, trajectories are such that collisions are disorientated and electrons follow energetically favourable paths. In effect, transport is independent of positional disorder.

Figure 6 .

 6 Figure 6. Schematization of the sandwich device. Note placement of electrodes to minimize possibility of short circuits.

Figure 7 .

 7 Figure 7.Apparatus for photodipolar study.

Figure 8 .

 8 Figure 8. Band scheme showing the position and depth of traps.

Figure 9 .

 9 Figure 9.

Figure 10 .

 10 Figure 10.

Figure 11 .

 11 Figure 11. Trap depths for samples exposed only during the cooling process to: (a) UV and natural light; and (b) natural light only.

Figure 12 .

 12 Figure 12.Cole-Cole plot of the ITO/Alq3/Al device at several bias voltages.

Figure 13 .

 13 Figure 13.Plots of log R p versus log V.

Figure 5 E

 5 Figure 5

Figure 8 conductionT

 8 Figure 8

  Figure 10

http://mc.manuscriptcentral.com/pm-pml Philosophical Magazine & Philosophical Magazine Letters


Julien Roussel

Michel Haritopoulos

Philippe Ravier

Olivier Buttelli

A New Cyclostationarity-Based Blind Approach for Motor Unit's Firing Rate Automated Detection in Electromyographic Signals

This work focuses on electromyographic (EMG) signal processing. We propose a new blind approach that aims at detecting the firing rates of the activated motor units. The proposed method is based on the fact that, EMGs can be modelled as second-order cyclostationary signals. After application of a Blind Source Separation (BSS) algorithm, we compute a cyclostationarity measure which is the Cyclic Spectral Density (CSD), and we show how one can use it to group the estimated components into independent subspaces and in an automated manner. The proposed classification procedure is based on the concept of subspace BSS techniques, like the Multidimensional Independent Component Analysis (MICA), the difference being that our method allows automatic classification of the estimated source signals. After discarding the subspace corresponding to the noise and computation of a modified CSD measure, the proposed procedure yields to the detection of specific cyclic frequencies corresponding to the discharge frequencies of the Motor Units Action Potential Trains (MUAPTs). Early results obtained from experiments on synthetic EMGs are presented in the paper and research perspectives conclude this work.

I. INTRODUCTION

Research on bioelectric signals is very active over these last twenty years and, in the meantime, new signal processing techniques emerged, offering new challenges. In particular, Blind Source Separation (BSS) [START_REF] Jutten | Blind separation of sources, part I: An adaptive algorithm based on neuromimetic architecture[END_REF] has been applied, e.g. for single muscle activity detection of surface electromyographic signals [START_REF] Farina | Blind Separation of Linear Instantaneous Mixtures of Nonstationary Surface Myoelectric Signals[END_REF], but also, for the estimation of the foetus' heartbeat rate and subspace dimension [START_REF] Haritopoulos | Cyclostationarity-Based Estimation of the Foetus Subspace Dimension from ECG Recordings[END_REF]. One of the most challenging applications of this technique concerns the exploration of muscle's electrical activity.

A muscle is composed of Muscle Fibres (MFs) organized into Motor Units (MUs). This functional unit is composed of an alpha-motoneuron (α-MN), innervating several MFs (from tens to hundreds MFs depending on the MU and on the muscle characteristics).

Activation of the MU produces an electric field generated by each MF into the MU. The summation of these electric fields provides a specific waveform called Motor Unit Action Potential (MUAP). This full electrical activity is called electromyogram (EMG) and can be recorded using electrodes located on the skin surface (sEMG). When this EMG is composed of several MUs activities it becomes difficult to distinguish the individual MUAPs.

The contraction of MFs requires a train of action potentials which induces a MUAP Train (MUAPT). This train produces a frequency discharge called Firing Rage (FR). In many cases, the FR evaluation of individual MUs is important to understand how the Central Nervous System (CNS) controls the MU and in the case of clinical application it provides information about neuromuscular disorder.

The paper is organised as follows. First, we present the cyclostationary nature of EMG signals. Next, is introduced the model we used to generate synthetic EMGs and the overall concept of BSS techniques; a particular focus is made on Multidimensional Independent Component Analysis (MICA). Follows a detailed presentation of the proposed automated estimation method and the results obtained after its application to simulated EMGs. A discussion concludes this work.

II. CYCLOSTATIONARY PROPERTIES OF MUSCLE

ACTIVITY Even under isometric conditions and in constant force, the MUAPT is not strictly periodic and has a mean Inter-Spike Interval (ISI) equal to the inverse of the FR. Instantaneous ISI is not fully constant over time; it exhibits a random variation called jitter [START_REF] Clamann | Statistical Analysis of Motor Unit Firing Patterns in a Human Skeletal Muscle[END_REF]. Finally, a MUAPT writes:

y(t) = ∑ i∈N x ( t - i F R + τ i ) (1)
where x stands for the MUAP waveform and τ i denotes the jitter. This signal exhibits a hidden periodicity at the FR, called cyclostationarity. It has been shown [START_REF] Roussel | Cyclostationary Analysis of Electromyographic Signals[END_REF] the considered model in ( 1) is a second-order cyclostationary signal (CS) that leads to a periodic Instantaneous Autocorrelation Function (IAF):

Γ xx (t, τ ) = E [ x ( t - τ 2 ) x ( t + τ 2 ) ] (2)
The two-dimensional Fourier transform of Γ xx (t, τ ) along t and τ provides the cyclic spectrum of the signal of interest, with α the cyclic frequency and f the spectral frequency, associated to t and τ , respectively. That leads to the Cyclic Spectrum Density (CSD) hereafter:

S xx (α, f ) = ∫∫ R 2 Γ xx (t, τ ) e -2iπ(tα+τ f ) dtdτ = E [ X ( f -α 2 ) X ( f + α 2 ) ] (3)
where x stands for the MUAP waveform and X denotes its Fourier transform. Considering a second-order cyclostationary signal, the periodicity in time of the IAF generates spectral lines along values of the cyclic frequency α. As we will demonstrate in what comes next, the CSD proves to be a useful tool in order to reveal hidden periodicities present in the MUAPT.

III. EMG SIGNAL PROCESSING

A. EMG Modelling

For the simulated EMG signals and the experiments present in this paper, we used (1) to generate each MUAP. Summation of the action potentials generated by the fibers corresponding to these MUAPs, leads to the following synthetic EMG model:

s EM G (t) = N ∑ i=1 y i (t) + ν(t) (4)
where N and i ∈ [1, N ] denote the number of active MUs and the MUAP index, respectively, whereas ν(t) stands for an iid Gaussian noise. The MUAPT y is computed following (1) and its jitter τ i is drawn from a normal distribution with zero mean and σ 2 i variance. According to Clamann's law [START_REF] Clamann | Statistical Analysis of Motor Unit Firing Patterns in a Human Skeletal Muscle[END_REF], standard deviation is computed following

σ i = (0.91/F R 2 i ) + 4 × 10 -3 , i ∈ [1, N ].
Finally, the simulated MUAPTs use a library template of synthetic MUAP waveforms based on model (4) (interested readers are referred to [START_REF] Farina | A Surface EMG Generation Model With Multilayer Cylindrical Description of the Volume Conductor[END_REF] for details).

B. Blind Source Separation

Given a set of M observed signals

x i (t), i ∈ [1, M ], BSS methods aim to extract the N unknown source signals s j (t), j ∈ [1, N ],
with N ≤ M , which are drowned in the observations contaminated by additive noise n(t):

x(t) = As(t) + n(t) (5)
where x(t) = [x 1 (t), x 2 (t), ..., x M (t)] † and s(t) = [s 1 (t), s 2 (t), ..., s N (t)] † denote the observations (also called mixtures), and the unknown source vector, respectively, with † the transpose operator and with A an unknown M × N full rank mixing matrix. Various methods for estimating the unmixing matrix depending on the conditioning of A and the number of source as well mixture vectors exist in the literature; one can compute the pseudo-inverse of A or use adaptive filters which avoid matrix inversion [START_REF] Sahin | A Method for Subsample Fetal Heart Rate Estimation Under Noisy Conditions[END_REF]. The model in ( 5) is known in the literature as the noisy linear instantaneous model and assumes statistical independence of the unknown source signals and at most one Gaussian source vector component. Regarding the noise, is generally assumed to follow a normal distribution.

C. Multidimensional Independent Component Analysis

The Multidimensional Independent Component Analysis (MICA) [START_REF] Cardoso | Multidimensional Independent Component Analysis[END_REF] consists of a linear separation of mixed signals into independent groups instead of solely single independent components (ICs). Its author applied this method to real foetal electrocardiogram (FECG) data. From a set of observations recorded with skin electrodes placed in the expectant mother's abdominal and thoracic areas, he first applies the BSS algorithm JADE [START_REF] Cardoso | Blind beamforming for non Gaussian signals[END_REF] to a three-dimensional set of these recordings to extract an equal number of independent components. Then, based on a simple visual inspection, the author groups two of them into a two-dimensional subspace corresponding to the maternal ECG (MECG); we will show in IV-C how to automate this classification step using the cyclostationary properties of the signal of interest.

IV. SIMULATED DATA AND METHOD

A. Generating Synthetic EMG Mixtures

For our experiments, we needed to construct a simulated EMG mixture vector. For this, we used (4) described in section III-A. Our surface EMG acquisition test bench consisting of seven equidistant surface electrodes, we took into account the slight delay with which each MUAPT arrives from the first towards the last sensor. Once the MUAPT delayed versions computed, they are mixed up with a real well conditioned (i.e. non singular) mixing matrix A EM G . Finally, a Gaussian noise g n (t) is added to each one of the input channels. Hence, the following model corresponds to the BSS noisy linear instantaneous one in (5):

x EMG (t) = A EM G s EMG (t) + g n (t) (6)
where s EMG (t) is the vectorial form of the unknown EMG signals in [START_REF] Clamann | Statistical Analysis of Motor Unit Firing Patterns in a Human Skeletal Muscle[END_REF].

The variables in our simulation procedure are:

• the number N of the activated MUs,

• the firing rates for each one of the activated MUs (in Hz),

• the size M of the observations vector x EMG , • the mixing matrix A EM G ,

• the jitter level as rate of the Clamann's law σ i in %, and, • the SN R expressed in dB (amount of noise g n ).

In the following and in order to clarify the presentation of the simulation results, the above variables are assigned the next values: N = 4 with respective firing rates F R i = {10.8, 11, 13.5, 13.8}Hz, M = 7, A EM G is a M ×N mixing matrix containing random values drawn from the normal distribution, jitter level in {10, 50, 100}%σ i and SN R in {-15, -10, -5}dB. For comparison purposes, the same mixing matrix A EM G and additive noise vector g n (t) have been used in all simulations. B. Why Use Cyclostationary Measures? Fig. 1 shows the time waveform of the raw MUAP library templates used in all simulations for this work. One can easily remark that, their respective shapes are all different (but, in general, they may also have some similarities), their amplitudes have a large dynamic range and, also, they may overlap in time. This is some of the major complexities that make decomposition or firing rates estimation tasks more difficult [START_REF] De Luca | Decomposition of Surface EMG Signals[END_REF].

Once the mixing vector computed according ( 6), combinations of the aforementioned complexities together with the strength of additive Gaussian noise of the mixing model and the amount of jitter, make EMG signal processing an even more challenging task. It is very hard to distinguish the individual MUAP shapes from the time plots of the x EMG mixture vector's individual components. Hence, we used envelope spectrum analysis of the observations and we compared the obtained results concerning FR estimation, with those obtained with the proposed method based on the intrinsic cyclostationary properties of EMG signals (envelope spectrum is issued from the Fourier transformed squared analytical signal of interest). As cyclostationarity measure, we used the integrated CSD (iCSD) obtained by summing over all the spectral frequencies f for every cyclic frequency α.

C. The Procedure for the Firing Rates detection

The following steps compose the proposed MU's firing rate automated detection procedure:

1) Apply JADE to the mixing vector x EMG (t) and obtain estimated independent components

JADE i , i ∈ [1, M ].
2) Compute the CSD and then the iCSD for each extracted independent component previously computed.

3) Compute and compare standard deviation and kurtosis

values of the CSDs and put into an independent subspace those corresponding to the noise. 4) For each iCSD computed in step 2, except for those corresponding to the noise subspace (step 3), subtract its maximum value. If the new vector exhibits null values, then, the ICs whose null values correspond to the same cyclic frequency α span a subspace of signal components corresponding to a MUAP firing at that cyclic frequency. The above proposed procedure employs one of the most widely used BBS algorithms (JADE) which is based on fourth-order statistics. Other BSS algorithms may be used for the separation task (step 1).

V. RESULTS

For the simulations, the variables are given the values detailed in section IV-A. In real world EMG signals, the number of active distinguishable MUs -even for minimum Maximum Voluntary Contraction (MVC) rates, is at least equal to several hundreds. But, for the sake of clarity and to test the feasibility of the proposed method, we have chosen N = 4.

A. A Concrete Case Simulation Example

Let us now illustrate the application of the proposed FR detection procedure by considering a simulated EMG mixture with a 100%σ i jitter and -10dB SN R. Envelope spectrum analysis of the x EMG (t) vector, reveals 2 among the 4 unknown, a priori, firing rates. Envelope spectrum analysis of the estimated ICs after application of the JADE algorithm, does not detect any additional FR. After applying the proposed procedure, one obtains the CSDs of the JADEseparated ICs. Now, and in order to decide whether an IC should fit the noise subspace, one computes the standard deviation and kurtosis (κ i , 1 ≤ i ≤ M ) values of the obtained CSDs. Obtained results are summarised in Table I.

The IC corresponding to the noise subspace is the second one, not only because its CSD's standard deviation value is the smallest one, but also, because of its CSD's low kurtosis value comparatively to those of the remaining ICs, which indicates a very noisy CSD plot. The CSDs of the remaining six ICs are plotted in Fig. 2; one can easily remark highvalued spectral lines at cyclic frequencies equal to 10.8Hz, 11Hz and 13.8Hz. Thus, the subspace containing useful information about the signal of interest is spanned by six components while the noise subspace is one-dimensional.

The detection of the previously detected firing rates is automated by computing the integrated CSDs of the sixdimensional subspace and then subtracting from each one of them its maximum value. Therefore, one obtains the plot of Fig. 3. The modified iCSDs of components 1, 3, 5, 7 exhibit a single null value at cyclic frequency α = 13.8Hz, the one of component 4 has a null at α = 11Hz and, finally, the iCSD of component 6 vanishes at α = 10.8Hz. These cyclic frequencies correspond to firing rates F R 1,2,4 (section IV-A). Only the F R 3 = 13.5Hz still remained undetectable most likely due to the relatively small amplitude of the third MUAP (Fig. 1).

B. Synthesis of the Obtained Results

Many different synthetic EMG mixtures have been tested. Table II resumes the obtained results with the variables' values given in section IV-A.

For each pair {SN R (rows), jitter (columns)}, the columns A, B and C of the table show the number of detected firing frequencies associated to the active MUs. The first two columns, A and B, correspond to the results given after visual inspection of the envelope spectrum of the raw mixtures, and the JADE-separated independent components, respectively, whereas, the third column C, gives the results after application of the procedure described earlier in section IV-C.

With 100%σ i jitter values and for SN R ratios smaller than -5dB, the proposed method achieves detection of all firing rates, except the one at 13, 5dB. In the worst case, it detects as much firing frequencies as with an envelope spectrum analysis after ICA separation of the raw data. The fact that the proposed method did not succeed to detect the remaining FR, is mainly due to the very low amplitude range of the associated MU with respect to these of the remaining MUs (dashed red curve of Fig. 1).

VI. DISCUSSION

In the last decade, various techniques for EMG decomposition have been proposed in the literature (e.g. [START_REF] Glaser | Real-Time Motor Unit Identification From High-Density Surface EMG[END_REF]). The work we present here is a novel method for estimating the number of MUs and their firing rates in surface EMGs. It takes advantage of the intrinsic cyclostationary properties of With the proposed method and under certain conditions one obtains a gain over traditional frequency domain signal processing techniques. Future research should focus on the validation of the proposed method's estimation accuracy and of its robustness against different BSS algorithms, when applied to simulated EMG mixtures, with more or less closely spaced FRs, with different numbers and various relative amplitude range for the MUs used for the simulated mixtures. Current research in that direction is ongoing. Also, its extension and application on real world EMG datasets is a very challenging task due to the important number of active MUs which can vary between ten to more than several thousands depending on the muscle.

Fig. 1 .

 1 Fig. 1. The 4 MUAP library templates used for the simulations.

Fig. 2 .

 2 Fig. 2. CSDs of 6 out of 7 estimated ICs using the JADE algorithm.

Fig. 3 .

 3 Fig. 3. Modified iCSD of all JADE-estimated ICs except the 2 nd one corresponding to the noise subspace.

TABLE I STANDARD

 I DEVIATION (σ CSD i ) AND KURTOSIS (κ) VALUES OF THE i th

	iCSD minus max(iCSD) for each JADE extracted component
		15
		14	Y: 13.8
	α (Hz)	13
	Cyclic frequency	11 12	Y: 10.8 Y: 11			JADE 1 JADE 4 JADE 5 JADE 3
		10				JADE 6
						JADE 7
		0 9	0.5	1	1.5	2	2.5	3
					Arbitrary unit
									INDEPENDENT COMPONENT'S CSD.
								IC i	1	2	3	4	5	6	7
								σ CSD i	0.36 0.02 0.34 0.07 0.19 0.05 0.33
								κ i	55.7	7.4	55.8	28.5	52	21.1	55.7

  such signals, which, at the best of our knowledge, has not been reported yet in the dedicated literature, and it introduces a new automated classification step of the BSS estimated components into independent subspaces. The obtained results after application of the proposed method to synthetic EMGs are very promising.

				TABLE II
		NUMBER OF DETECTED MOTOR UNITS.
					Jitter (%σ i )
			10		50			100
	SNR	A	B C	A	B C	A	B C
	-5dB	2	3	3	3	3	3	3	3	3
	-10dB	2	2	3	2	2	3	2	2	3
	-15dB	1	2	3	1	2	3	1	1	3

ACKNOWLEDGMENT

Authors would like to thank Prof. Dr. Dario Farina, Director of the Department of Neurorehabilitation Engineering at the University Medical Center of Goettingen, Germany, for having kindly provided us code for action potential simulation.


Shantanu Das

Dariusz Dereniowski

Adrian Kosowski

Przemysław Uznański

Rendezvous of Distance-aware Mobile Agents in Unknown Graphs *

Keywords: Mobile Agent, Rendezvous, Synchronous, Anonymous Networks, Distance Oracle, Lower Bounds

We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size and to depend only on the initial distance between the agents and some local parameters such as the degree of the vertices, and the size of the agent's label. It is well known that even for simple graphs of degree ∆, the rendezvous time can be exponential in ∆ in the worst case. In this paper, we introduce a new version of the rendezvous problem where the agents are equipped with a device that measures its distance to the other agent after every step. We show that these distance-aware agents are able to rendezvous in any unknown graph, in time polynomial in all the local parameters such the degree of the nodes, the initial distance D and the size of the smaller of the two agent labels l = min(l 1 , l 2 ). Our algorithm has a time complexity of O(∆(D + log l)) and we show an almost matching lower bound of Ω(∆(D + log l/ log ∆)) on the time complexity of any rendezvous algorithm in our scenario. Further, this lower bound extends existing lower bounds for the general rendezvous problem without distance awareness.

Introduction

Overview

Suppose two friends travel to a distant land and arrive at a city where all road signs are written in a language unknown to either of them. If the friends get separated and can no longer communicate with each-other, how could the two friends get together again without any help from a third person. This problem of gathering two autonomous mobile agents, called the rendezvous problem has been studied in many different contexts, for example for two ships lost in the sea, two astronauts that land in separate parts of a planet and so on. Initial studies on the problem were restricted to finding probabilistic strategies for movement of the two agents that minimize the expected time to rendezvous (See [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF] for a survey of such results). In recent years, the deterministic version of the problem has received a lot of attention especially by the distributed computing community. The rendezvous problem for two agents moving along the edges of a graph is a typical problem of symmetry breaking and it is a primitive for distributed coordination among autonomous mobile robots. The solution to the problem depends on the structure of the graph, the capabilities of the agents and the initial knowledge available to the agents. In this paper, we consider the problem for deterministic agents with local vision moving in an initially unknown graph; the problem is solved when the two agents are simultaneously located in the same vertex. We are interested in the worst case time complexity for rendezvous. In general, rendezvous cannot always be solved deterministically when the underlying graph is highly symmetric and the agents follow identical strategies. A typical example is that of a ring network with unlabelled nodes where the two agents are placed on opposite vertices on any diameter. In this case, the distance between the two agents may never decrease if the agents use identical strategies, moving left or right at the same time.

Known solutions to the rendezvous problem are based on one of the following two approaches. The first type of solutions relies on finding a point of asymmetry in the graph and meeting at a unique point of asymmetry (e.g. such a point of asymmetry always exists in graphs where the nodes are labelled uniquely). The second type of solutions assumes that the agents are provided with distinct labels and thus, they can execute distinct strategies and ensure rendezvous. The former type of results require the agents to traverse every edge of the graph in the worst case and the time to rendezvous depends on the size of the graph. On the other hand, the latter type of solutions allow the agents to rendezvous in graphs of arbitrary size or even infinite graphs when the agents are located a finite distance apart. It has been shown that rendezvous of agents with distinct labels can be achieved in arbitrary finite graphs in time polynomial in the size of the graph and the size of the smaller of the labels assigned to the agents both in the synchronous case [START_REF] Kowalski | How to meet in anonymous network[END_REF][START_REF] Ta-Shma | Deterministic rendezvous, treasure hunts and strongly universal exploration sequences[END_REF] and the asynchronous case [START_REF] Dieudonné | How to meet asynchronously at polynomial cost[END_REF]. For infinite graphs, the only known results are for very specific graphs such as lines [START_REF] Stachowiak | Asynchronous Deterministic Rendezvous on the Line[END_REF] or grids [START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF]. For a ∆-dimensional infinite grid, the optimal time to rendezvous is Θ(D ∆ ) which is already exponential in the maximum degree of the graph. In fact, in unknown graphs of degree ∆, where the agents start a distance of D apart, an agent may have to visit all vertices at a distance of D from its initial location. Since there could be D ∆ such vertices, the time cost of rendezvous would be exponential in ∆, even if the agents have complete knowledge of the graph as well as the initial distance between them. Thus the question is what additional capabilities would enable the agents to rendezvous in polynomial time.

In this paper we are interested in designing the simplest mechanism that can help the agents to rendezvous in a large (possibly infinite) graph in time polynomial in the other parameters of the problem, e.g. the initial distance, the maximum degree of the graph and the labels assigned to the agents. We achieve this by equipping the agents with a device that can measure the distance to the other agent in the graph after each step of the algorithm1 . In fact, our algorithm does not require knowledge of the exact distance between the agents, but instead it is sufficient if the agent can detect whether the distance to the other agent increased or decreased after each move. We assume time to be discretized into rounds; in each round an agent can either traverse one edge of the graph or stay at its current location, and at the end of each round the agent can determine whether the distance to the other agent increased, decreased or remained unchanged during this round. Note that the agents have no means of detecting the direction leading to the other agent. We call agents equipped with the above device distance-aware agents. We show that distanceaware agents can rendezvous in arbitrary graphs in time polynomial in the initial distance, in the degree of the graph, and in the size of the smaller of the two agent labels.

Our Contributions

We show that two distance-aware agents, starting from an initial distance D apart from each other in a connected graph with maximum degree ∆, can rendezvous in time O(∆ • D + ∆ • log l) rounds, where l = min(l 1 , l 2 ) and l 1 and l 2 are the labels of the agents. The proof is constructive and provides a deterministic algorithm for the agent that takes as input the label of the agent. The algorithm does not require any prior knowledge of the graph and works for any connected graph. We also show that our algorithm is almost optimal by providing a lower bound of Ω(∆(D + log l/ log ∆)) for rendezvous of distance-aware agents. Thus, our algorithm is asymptotically optimal when the maximum degree ∆ is not extremely large.

The lower bound presented in this paper holds even for agents that can compute the exact distance to each other at every step, while the algorithm requires only the knowledge of changes in distance. Moreover, this lower bound extends existing lower bounds for the general problem of rendezvous of labelled agents in unknown graphs. In terms of the size of agent labels, the previous lower bound (without distance awareness) was Ω(log l • D) which already holds for the ring; no generalizations of this lower bound to graphs of arbitrary degree have been presented before. Our results show that the lower bound for rendezvous must be at least Ω(log l(D + ∆/ log ∆)).

Related Work

This paper considers the deterministic version of rendezvous (for randomized solutions see e.g. [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF]). The problem of rendezvous of autonomous mobile agents has been studied for agents moving in a discrete space i.e. a graph [START_REF] Pelc | Deterministic rendezvous in networks: A comprehensive survey[END_REF] or those moving on a continuous space (e.g. two dimensional plane [START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF]). In the graph setting, rendezvous of identical agents is possible only if the graph is asymmetric or the agents are placed in asymmetric positions on the graph. There exists a characterization of such instances (graphs and initial positions of agents) where rendezvous is solvable [START_REF] Yamashita | Computing on anonymous networks: Part I-Characterizing the solvable cases[END_REF]. If the agents are asynchronous, they can take advantage of the asymmetry in their initial positions by marking their initial position by a pebble [START_REF] Baston | Rendezvous search when marks are left at the starting points[END_REF][START_REF] Kranakis | The mobile agent rendezvous problem in the ring[END_REF]. On the other hand, if the agents have distinct labels then rendezvous is possible in any graph and any starting positions, without the need to mark nodes. The first deterministic synchronous rendezvous algorithm for agents with distinct labels was presented by Dessmark et al. [START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF] and the time complexity of the algorithm was O(n 5 √ τ log l log n + n 10 log 2 n log l) for a graph of n nodes, where τ is the delay in the starting time of the agents. Subsequent studies [START_REF] Kowalski | How to meet in anonymous network[END_REF][START_REF] Ta-Shma | Deterministic rendezvous, treasure hunts and strongly universal exploration sequences[END_REF] improved this result and removed the parameter τ from the time complexity allowing for rendezvous in time polynomial in both n and log l. For the asynchronous case, De Marco et al. [START_REF] Marco | Asynchronous deterministic rendezvous in graphs[END_REF] provided an algorithm for rendezvous with a cost of O(D • log l) rounds, when the graph is known. For unknown arbitrary graphs, Czyżowicz et al. [START_REF] Czyżowicz | How to meet asynchronously (almost) everywhere[END_REF] gave the first algorithm for asynchronous rendezvous but the cost of this algorithm is at least exponential in the distance D and the degree ∆ of the graph. Recently, Dieudonné et al. [START_REF] Dieudonné | How to meet asynchronously at polynomial cost[END_REF] provided an improvement over this result achieving asynchronous rendezvous in time polynomial in n and log l. Rendezvous of agents starting from a finite distance D in an infinite graph has been studied for the special cases when the graph is a line [START_REF] Marco | Asynchronous deterministic rendezvous in graphs[END_REF][START_REF] Stachowiak | Asynchronous Deterministic Rendezvous on the Line[END_REF] or a grid [START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF], assuming that the agents have a sense of orientation and they know their own location in the labelled grid.

There have been several studies on the minimum capabilities needed by the agents to solve rendezvous. For example, the minimum memory required by an agent to solve rendezvous is known to be Θ(log n) for arbitrary graphs. Czyżowicz et al. [START_REF] Czyżowicz | How to meet when you forget: Log-space rendezvous in arbitrary graphs[END_REF] have provided a memory optimal algorithm for rendezvous, and there are studies on the tradeoff between time and space requirements for rendezvous [START_REF] Czyżowicz | Time vs. space trade-offs for rendezvous in trees[END_REF]. In some papers, additional capacities are assumed for the agents to overcome other limitations, e.g. global vision is assumed to overcome memory limitations [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] or the capability to mark nodes using tokens [START_REF] Kranakis | The mobile agent rendezvous problem in the ring[END_REF] or whiteboards [START_REF] Chalopin | Rendezvous of Mobile Agents in Directed Graphs[END_REF] is often used to break symmetry. The model used in this paper can be seen as a special case of the oracle model for computation [START_REF] Fraigniaud | Oracle size: A new measure of difficulty for communication problems[END_REF] where the agent is allowed to query an oracle that has global knowledge of the environment. However in our case, since the only queries are distance queries, the oracle can be implemented without complete knowledge of the graph topology.

Model and Notations

We model the environment as an undirected connected (possibly infinite) graph G(V, E). The nodes of V are unlabelled such that vertices of the same degree look identical to any agent (i.e. the nodes are anonymous). At each node of the graph, the edges incident to it are locally labelled, so that an agent arriving at a node can distinguish among them2 . We assume that edges incident to a node v are labelled by distinct integers (called port numbers) from the set {1, 2, . . . , d(v)}, where d(v) is the degree of node v. The degree of each node is finite and bounded by the parameter ∆ (which is unknown to the agent). For any two distinct vertices u, v ∈ V , the distance between them, denoted by dist(u, v), is the number of edges in any shortest path from u to v in G.

There are exactly two agents a 1 and a 2 , and each agent a i has a distinct label ℓ(A i ) ∈ {0, 1, . . . , L -1} for some integer L ≥ 1. An agent knows its own label but not that of the other agent. The agents have no prior knowledge of the graph. Each agent starts from a distinct node of the graph and moves along the edges of the graph in synchronous steps following a deterministic algorithm. In other words, time is discretized into regular intervals called rounds; in each round, an agent at a node v can either move to an adjacent node of G or remain stationary at v. If the agent moves to an adjacent node w, the agent becomes aware of the port number of the edge through which it entered w. The agent has no means of marking a node that it visits and the agents cannot communicate with each other. An agent can see the other agent only when both agents are on the same node (in particular the agents do not see each other if they cross on the same edge from opposite directions). The two agents start the algorithm in the same round (called round 0) and rendezvous is achieved in the earliest round T when the two agents are at the same node. We denote by D the distance between the starting locations of the agents.

Contrary to previous studies on rendezvous, we assume that the agent is equipped with a device that measures the distance to the other agent. An agent at a node v in round t can make a query to this device (modelled as a function call distance()) which returns the value dist(v, u), where node u is the location of the other agent in this round. In each round the agent can make one call to distance() and depending on the value returned, the value of the agent's label, the current state of the agent, and the degree of the current node, the agent chooses a number between 0 and d(v) and leaves the current node v through this port. We assume that the port number 0 corresponds to a self-loop at node v and if the agent chooses 0 it remains at the same node v. In this paper we do not restrict the memory of an agent in any way. Thus, the agent can memorize its complete history of moves up to the current round and store this as its internal state.

Lower Bound for Distance-aware Rendezvous

In this section we provide lower bounds on the rendezvous time for distance-aware agents. Observe that a trivial lower bound is Ω(D) since at least one of the two agents must traverse D/2 edges to achieve rendezvous. We could easily obtain a better lower bound for graphs of degree ∆. The result below is folklore and we include it only for completeness. Lemma 3.1 Rendezvous of two agents that are initially at a distance of D apart in an unknown graph of maximum degree ∆ requires Ω(D • ∆) rounds in the worst case.

Proof : Consider the caterpillar graph shown in Figure 1 obtained by taking a line of D + 1 nodes and replacing each node with a star of size ∆ -1. Suppose that the two agents start at the endpoints of the path of length D in this graph, as shown. If an agent traverses an edge leading to one of the leaves, it has no other option than to return and try another port. For any deterministic algorithm, an adversary can assign the port numbers in such a way that the agent needs to traverse all the ∆ incident edges before it gets any closer to the other agent. Thus after 2∆ -1 rounds the agents can reduce the distance between them by 2. Using a repetition of this argument, the result follows. The above lower bound is independent of the agent's labels. We now present a bound which includes the parameter L which bounds the size of the set of possible agent labels. It is known that rendezvous of two agents with distinct labels requires Ω(log L) rounds [START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF]. However this lower bound is for the simplest graph consisting of two nodes and a single edge connecting them. We provide below a better lower bound for arbitrary graphs of maximum degree ∆.

Our method is constructive, i.e., given a deterministic rendezvous algorithm A, we describe a graph and a procedure for the adversary to label the ports in a graph and to choose starting positions that will keep the agents executing A from meeting for the desired time period. Definition 3.1 A k-clique-p-butterfly is a (k + 3)-regular graph on (k × p) vertices (denoted by v 0,0 , . . ., v k-1,p-1 ), constructed as follows:

• for each 0 ≤ j < p, we connect all pairs of vertices from v 0,j , v 1,j , . . . , v k-1,j (so they form a k-vertex clique, named j-th clique),

• for any given 0 ≤ j, j ′ < p, 0 ≤ i, i ′ < k, we connect v i,j and v i ′ ,j ′ if j ′ = (j + 1) mod p and i ′ ∈ {2i mod k, (2i + 1) mod k}. For two vertices, v from j-th clique and v ′ from j ′ -th clique, we say that their horizontal distance is min((j -j ′ ) mod p, (j ′ -j) mod p). By the properties of the butterfly-type interconnections between the cliques, we observe that, if for two vertices the horizontal distance is at least log k, then their actual distance in the graph is equal to the horizontal distance. See Figure 2 for an example of a k-clique-p-butterfly graph where the agents are at a distance D > log k. Theorem 3.1 For any odd k ≥ 3 and p ≥ 2 • ⌊log k⌋, given a k-clique-p-butterfly (denoted further as G), for any deterministic algorithm A, and integers L > 0 and D ≥ log k = log(∆ -3), there exist labels 0 ≤ ℓ(1), ℓ(2) < L and a port numbering of G such that if two agents with these labels start at two vertices at distance D in this graph, they will remain at distance D for at least Θ(∆ log L/ log ∆) steps.

j = 0 j = 1 j = D j = p -1
Proof : The main idea of the proof is as follows. We will choose four special port numbers that will be assigned in every vertex to the "bridge" edges connecting it to an adjacent clique (two ports to advance to the next clique and two ports to go backward). Note that moving inside the clique doesn't change the distance to the other agent. By carefully picking the agent labels, we will ensure that both agents will choose the forward ports at the same rounds and the backward ports also at the same rounds, thus they will maintain a constant distance between themselves, for a sufficient amount of time and during this time period, any queries to the distance oracle would be useless.

Before we proceed to prove the theorem, we need to fix some notation and provide some basic lemmas. We will consider the k-clique-p-butterfly graphs with a special type of port numbering where the ports on the two ends of each edge always form one of the pairs of values: {1, ∆}, {2, ∆-1}, . . . , {∆/2, ∆/2 + 1}. In other words, whenever an agent chooses to leave a node by port j, it arrives at the adjacent node by port ∆ + 1 -j. In a ∆-regular graph with such a port numbering, an agent can never distinguish between any two vertices and it can learn nothing new about the graph by traversing it. Thus, the algorithm A must choose a predefined sequence of ports to follow during the first t > 0 rounds when the distance between the agents remains D. For every 0 ≤ ℓ < L we denote the sequence of ports chosen by algorithm A (with input label ℓ) by (P ℓ (i)) i<t i=0 .

Lemma 3.2 There exist p 1 , p 2 , 0 < p 1 , p 2 ≤ ∆/2, and a set L ⊂ {0, 1, . . . , L -1}, |L| ≥ L/2, such that for each ℓ ∈ L, at most 8t/∆ elements of (P ℓ (i)) i<t i=0 are equal to one of the four values {p 1 , p 2 , ∆ + 1 -p 1 , ∆ + 1 -p 2 } (in total). Proof : In G, the port numbers on the edges are paired together as follows: {1, ∆}, . . . , {∆/2, ∆/2+ 1}. For each pair {p, ∆ + 1 -p}, let S p be the number of pairs (i, ℓ),

0 ≤ i < t, 0 ≤ ℓ < L, such that P ℓ (i) ∈ {p, ∆ + 1 -p}. Since S 1 + S 2 + • • • + S ∆/2 ≤ t • L, there must exist p 1 , p 2 such that S p 1 + S p 2 ≤ t • L • 2/(∆/2)=t • L • 4/∆.
Thus, there must exist a subset L containing at least half of the possible labels, such that for each ℓ ∈ L, the number of i's for which

P ℓ (i) ∈ {p 1 , p 2 , ∆ + 1 -p 1 , ∆ + 1 -p 2 } is not greater than 2 • t•L•4/∆ L = 8t/∆.
Given the ports p 1 and p 2 as in the lemma above, the adversary can assign the pairs of port numbers (p 1 , ∆ + 1 -p 1 ) and (p 2 , ∆ + 1 -p 2 ) to those edges of G that connect two adjacent cliques, such that ports p 1 and p 2 will take an agent forward to the next clique, ports ∆ + 1 -p 1 and ∆ + 1 -p 2 would take an agent backward to the previous clique and any other port will keep an agent within the same clique. We partition the set of port numbers into the subsets:

A = {p 1 , p 2 }, B = {∆ + 1 -p 1 , ∆ + 1 -p 2 }, C = {0, 1, . . . ∆} \ (A ∪ B).
Informally, the ports in A take an agent one step ahead, the ports in B take it one step back, and the C ports keep it in the same clique.

Lemma 3.3 There exist 0 ≤ ℓ(1) < ℓ(2) < L such that ∀i ≤ ⌊ log L 2 log ∆ ⌋ • ∆ 8 , P ℓ(1) (i) ∈ A iff P ℓ(2) (i) ∈ A, and (1)
P ℓ(1) (i) ∈ B iff P ℓ(2) (i) ∈ B. (2)
Proof : Let t > 0 be the first round such that for i = t, either (1) or ( 2) does not hold for any possible pair of labels ℓ(1) and ℓ(2) from the set {0, 1, . . . , L -1}. We will bound the value of t. Note that the sequence of ports (P ℓ (i)) i<t i=0 can be written as a sequence of A,B and C's. We choose the set of labels L from Lemma 3.2 and for any ℓ ∈ L, let us count the number of possible sequences (P ℓ (i)) i<t i=0 which correspond to distinct words from the alphabet {A, B, C}; let us denote this number as X. Recall that any such sequence can have at most 8t/∆ A-ports and B-ports in total (cf. Lemma 3.2). Assuming for the sake of notation that T = 8t/∆ is an integer and using Stirling's approximation, we get:

X = ⌊T ⌋ i=0 t i • 2 i ≤ 1 + T • t T • 2 T ≤ 1 + T • (2t) T (8t/∆)! ≤ 1 + T • 2t 8t/∆ • 1 e T = 1 + T e 4 ∆ T .
Since for any two labels in L the algorithm chooses distinct sequences, we have L/2 ≤ |L| ≤ X, which gives us T ≥ ⌊ log L 2 log ∆ ⌋ and thus t ≥ ⌊ log L 2 log ∆ ⌋ • ∆ 8 . We now return to the proof of the Theorem 3.1. From Lemma 3.3, we know that there exist two agents with labels ℓ(1), ℓ(2) such that these agents, when executing algorithm A, will use the ports going forward or backward simultaneously during the first t = ⌊ log L 2 log ∆ ⌋ • ∆ 8 rounds. Since the distance in the graph is independent of relative positions inside cliques (for D ≥ log k), the distance between agents is maintained to be D for at least t = Θ(∆ log L/ log ∆) steps.

The results of this section provide a lower bound of Ω(∆(D + log L/ log ∆)) rounds for rendezvous of distance-aware agents.

agent sequentially explores all ports at v (Note that the value of 2 ⌈log 2 d(v)⌉ exceeds the degree of v). The above process is interrupted whenever the agents observe that the distance between them decreased, and the procedure returns success in that case. Let v be the currently occupied node.

for l ← 0 to ⌈log 2 d(v)⌉ -1 do s ← TestPorts(2 l , 0) if s = success then return success end if end for s ← TestPorts(2 ⌈log 2 d(v)⌉ , b) return s
The observation given below follows directly from the formulation of procedure BoundDegrees.

Observation 1 Suppose that agent A i occupies node v i , i ∈ {1, 2}, and executes procedure BoundDegrees at the beginning of round r. If procedure TestPorts does not return success in the first j iterations of BoundDegrees, then:

(i) A i occupies v i at the end of the j-th iteration of BoundDegrees, (ii) both agents end the execution of the j-th iteration in round r + 2 j -1.

Denote I 0 = (0, 1] and I j = (2 j-1 , 2 j ] for j ≥ 1. We say that two nodes u and v are similar if there exists j ≥ 0 such that d(u) ∈ I j and d(v) ∈ I j . Lemma 4.1 Let r be some integer. Suppose that agent A i is present at v i , i ∈ {1, 2}, and calls in round r procedure BoundDegrees with input value b i . Then: This guarantees that the latter calls to TestPorts return success, which completes the proof of (ii). We now prove (i). Let b 1 = b 2 = 1. We argue that if the nodes v 1 and v 2 are not similar, then the call to BoundDegrees results in returning success. Suppose without loss of generality that d(v i ) ∈ I j i , i ∈ {1, 2}, where j 1 < j 2 . The number of iterations of the 'for' loop of procedure BoundDegrees executed by A i is ⌈log 2 d(v i )⌉ = j i , i ∈ {1, 2}. Thus, by Observation 1(i), A i occupies v i at the end of j 1 -th iteration of BoundDegrees for each i ∈ {1, 2}. Moreover, by Observation 1(ii), after finishing the execution of the 'for' loop, A 1 calls TestPorts(2 j 1 , b 1 ) while A 2 calls TestPorts(2 j 1 , 0) in the (j 1 + 1)-st iteration of the 'for' loop of BoundDegrees. Also, both of the above-mentioned calls to TestPorts are made in the same round r ′ . By similar arguments as when proving (ii), we obtain that condition (i) holds.

(i) for b 1 = b 2 = 1,
Note that if procedure BoundDegrees returns success, then the agents get closer, and we can repeat the same process for at their current locations. However, for some nodes procedure BoundDegrees may return failure and then procedure CompareLabels described below (see Algorithm 3) helps to break the symmetry. Procedure CompareLabels uses the notion of extended Algorithm 3 Procedure CompareLabels Input: None. Output: ξ(ℓ) i such that i is distinguishing for the extended labels of the agents.

Let ξ(ℓ) be the extended label of the executing agent. for i ← 1 to ⌈log 2 ξ(ℓ)⌉ do s ← BoundDegrees(ξ(ℓ) i ) if s = success then return ξ(ℓ) i end if end for labels. The extended label ξ(ℓ) of a label ℓ is an integer whose j-th bit is defined as follows:

ξ(ℓ) j =      ℓ ⌈j/2⌉ , for j ∈ {1, 3, 5, . . . , 2⌈log 2 ℓ⌉ -1}, 1,
for j = 2⌈log 2 ℓ⌉, 0, otherwise.

The index j = 2⌈log 2 ℓ⌉ is called the terminating bit of ξ(ℓ) (this is the last bit set to 1). Informally, the odd positions of the extended label are the the bits of ℓ while the even positions are all zeros, except for the terminating bit. We say that an index i is distinguishing for two extended labels ξ(ℓ) and ξ(ℓ

′ ) if ξ(ℓ) i = ξ(ℓ ′ ) i .
Informally, procedure CompareLabels iterates over the bits of the extended label of the executing agent in order to find an index i that is distinguishing for the extended labels of the two agents. The construction of extended labels guarantees that there exists a distinguishing index i not greater than the smaller length of the two extended labels and hence BoundDegrees returns success at the latest in the i-th iteration of the 'for' loop of procedure CompareLabels (the formal proof is given later; we remark here that if we used the label instead of the extended label, then the number of iterations of the 'for loop' would have to be equal to the length of the greater label to ensure rendezvous).

We postpone the analysis of procedure CompareLabels (given in Lemma 4.2) as it depends on the context at which it is called by the main procedure.

We finally describe the main procedure Rendezvous (see Algorithm 4). We start with its intuitive description. The first 'while' loop iteratively calls procedure BoundDegrees(1) as long as its execution gets the agents closer to each other. If a call to BoundDegrees(1) does not achieve that, then (as we formally prove later) the agents observed the same distance between each other while both explored all ports at their respective locations. This is significant as both agents learn j ′ ≤ j. The last execution of procedure BoundDegrees preceding the call to CompareLabels returns failure. Hence, if ξ(ℓ(A 1 )) j ′ = ξ(ℓ(A 2 )) j ′ = 1, then the j ′ -th call to BoundDegrees returns failure. Clearly, if ξ(ℓ(A 1 )) j ′ = ξ(ℓ(A 2 )) j ′ = 0, then the agents stay idle during the j ′ -th call to procedure BoundDegrees which also implies that it returns failure.

Thus, the above proves that the j-th call to procedure BoundDegrees takes place during the execution of procedure CompareLabels and, by Lemma 4.1(ii), it returns success for both agents. Thus, procedure CompareLabels returns the respective bits of the extended label at position that is distinguishing, which completes the proof. Proof : We first prove that the execution of procedure Rendezvous guarantees rendezvous. If the agents rendezvous during the execution of the first 'for' loop, then the claim follows and hence suppose that this is not the case. Denote by b i the value of the variable b returned by the call to procedure CompareLabels by agent A i , i ∈ {1, 2}. By Lemma 4.2, b 1 = b 2 . Let without loss of generality, b 1 = 0 and b 2 = 1. This implies that the agent A 1 stays idle indefinitely. The agent A 2 , during execution of procedure BoundDegrees(b 2 ) called in the second 'for' loop of procedure Rendezvous, explores all ports of the currently occupied node. Thus, the distance between agents decreases in some round which implies that each such call to procedure BoundDegrees(b 2 ) returns success. Thus, the agents rendezvous eventually. Now we analyze the rendezvous time. Each call to BoundDegrees takes O(∆) rounds. Moreover, each such call, except for at most one, made directly by procedure Rendezvous ensures that the distance between the agents decreases. This follows immediately for calls to BoundDegrees preceding the call to procedure CompareLabels since those calls, possibly except for the last one, return success. As for the remaining calls to BoundDegrees, the above claim is due to the fact that the input values are different for both agents due to Lemma 4.2. Thus, the total number of rounds due to all calls to BoundDegrees made directly by procedure Rendezvous is O(∆•dist(v 1 , v 2 )). The number of iterations of the 'for' loop of procedure CompareLabels is O(min{log ℓ(A 1 ), log ℓ(A 2 )}), each resulting in O(∆) rounds (the call to BoundDegrees).

Conclusions

This paper presented a new model for mobile agent computation by providing the agents with the capability of measuring distances to each other (or detecting changes in distances) at each step. We show that this simple mechanism allows us to reduce the time to rendezvous from exponential to polynomial in the degree of the graph. Assuming that such a distance measuring device is available to the agents, one could ask what other problems can be solved more easily using this additional capability. For example, the agents could use this mechanism for communication at distance by moving back and forth, when there are no other means of communication. This opens up a new area of research which is worth investigating.

Figure 1 :

 1 Figure 1: The two agents are located at the specially marked nodes at the two ends of a Caterpillar graph.

Figure 2 :

 2 Figure 2: A k-clique-p-butterfly graph where the two agents are located at the marked nodes at a distance D > log k.

Algorithm 2

 2 Procedure BoundDegrees(b) Input: An integer b ∈ {0, 1}. Output: success or failure.

  if both calls to BoundDegrees return failure, then the nodes v 1 and v 2 are similar, and (ii) if b 1 = b 2 and v 1 and v 2 are similar, then both calls to BoundDegrees return success.Proof : We first prove (ii). Suppose without loss of generality that b 1 = 1 and b 2 = 0. Since the nodes v 1 and v 2 are similar, x = ⌈log 2 d(v 1 )⌉ = ⌈log 2 d(v 2 )⌉ and therefore the executions of procedure BoundDegrees have the same number of iterations of the 'for' loop. If, in one of those iterations, the execution of procedure BoundDegrees ends, then (ii) holds and hence suppose that this is not the case. Thus, the calls to TestPorts(2 x , b 1 ) and TestPorts(2 x , b 2 ) are made by the agents. Moreover, by Observation 1, both calls are made in the same round and when agent A i is at v i , i ∈ {1, 2}. During these calls, A 2 stays idle during 2 x+1 rounds (because b 2 = 0) while A 1 explores all ports at v 1 during the same 2 x+1 rounds (because b 1 = 1 and 2 ⌈log 2 d(v 1 )⌉ ≥ d(v 1 )).

Theorem 4 . 1

 41 Suppose that agent A i with label ℓ(A i ) initially occupies node v i , i ∈ {1, 2}. Procedure Rendezvous guarantees that A 1 and A 2 rendezvous within O(∆ • (D + min i {log ℓ(A i )})) rounds where D = dist(v 1 , v 2 ).

Such a device can be implemented in practice e.g. by emitting specific signals at periodic intervals and measuring the intensity of the signal received from the other device held by the other agent.

Such an assumption is necessary to allow the agent to navigate in the graph.

* This work was done when the second and the third author were visiting the LIF laboratory in Marseille. Research partially supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201, by the ANR project DISPLEXITY (ANR-11-BS02-014) and by the ANR project MACARON (ANR-13-JS02-0002-01). Dariusz Dereniowski was partially supported by a scholarship for outstanding young researchers funded by the Polish Ministry of Science and Higher Education.

Upper Bound and Algorithm for Rendezvous

In this section we provide an algorithm that guarantees rendezvous of two distance-aware agents in O(∆(D + log l)) rounds. The algorithm is divided into four procedures. For each procedure, first we provide some intuitions on its behavior, then we give its formal description in the form of pseudo-code. After the descriptions of all procedures, the proof of correctness and analysis of rendezvous time of the algorithm are given.

We start with a procedure TestPorts (see Algorithm 1), which attempts to decrease the distance between the two agents. The input consists of a positive integer δ and a bit b ∈ {0, 1}. Recall that the command distance() performs the oracle query and provides the current distance from the other agent. We also introduce a command move(x), where x is an integer, which behaves as follows. If x ∈ {1, . . . , d(v)}, where v is the node currently occupied by the executing agent, then move(x) forces the executing agent to move from v by taking port x, and the value returned by the move(x) command is the entry port at the arrival node. Otherwise, that is when x / ∈ {1, . . . , d(v)}, the executing agent stays idle in the given round, and move(x) returns 0. (We pass 0 as an argument to deliberately make an agent idle.) Algorithm 1 Procedure TestPorts(δ, b) Input: Two integers δ ≥ 1 and b ∈ {0, 1}. Output: success if the distance between agents decreases in some round; failure otherwise. The interpretation of the input variable b is that whenever b = 0, then the agent does not perform any movements during the execution of TestPorts. Note that if b = 1, then move(i • b) forces an agent to move only if there exists an edge with port i at v.

Suppose that, in the same round, both agents perform calls to procedure TestPorts with input parameters δ 1 , b 1 and δ 2 , b 2 , respectively. We will always ensure that δ = δ 1 = δ 2 . Informally, b 1 = b 2 = 1 implies that both agents iteratively take ports 1, . . . , δ (skipping the ones not present at the current node), ending the process if the distance between them decreases. Clearly, if b 1 = b 2 = 0, then both agents just stay idle during the 2δ rounds and the procedure returns failure. If b 1 = b 2 , then one agent stays idle while the other 'tests ports'. If we ensure that δ exceeds the degree of the node occupied by the agent that performs the movements, then the procedure will return success whenever b 1 = b 2 .

We now describe a procedure BoundDegrees with input variable b ∈ {0, 1} (see Algorithm 2). Informally speaking, for each 2 l such that 2 l < d(v), where v is the node occupied at the beginning of the execution of the procedure, the executing agent stays idle for 2 l+1 rounds (this is achieved by the call to TestPorts(2 l , 0). This part is independent of b. Then, TestPorts(2 ⌈log that they occupy nodes whose degrees are in the same interval I j for some j ≥ 0. In other words, the agents learn an asymptotically tight upper bound on both degrees. Then, procedure CompareLabels is called and uses the above fact as well as the labels of the agents to break the symmetry that occurs at the current agents' nodes. Note that CompareLabels returns either 0 or 1 and in this case different values are returned for both agents (see Lemma 4.2 below). Thus, the agent whose execution of CompareLabels returned 0 stays idle from now on. The other agents continues making calls to BoundDegrees(1) and since each execution results in exploring all ports at the currently occupied node, each execution gets the agent one step closer to the one that is idle. We also remark that the respective calls to procedure BoundDegrees in the second 'while' loop of CompareLabels are not necessarily 'synced', that is, the j-th of those calls can be made in different rounds by the agents. This, however, is not important as one of the agents stays idle and the other one performs appropriate movements. Proof : Since both agents call CompareLabels, none of the preceding calls to procedure BoundDegrees returns success and the agents do not rendezvous prior to the call to CompareLabels. By Observation 1 and a simple inductive argument, the calls to procedure CompareLabels made by both agents end in the same round r.

It remains to prove that the calls to CompareLabels return different values. By Lemma 4.1(i), at the beginning of round r the agents A 1 and A 2 are, respectively, at two similar nodes v 1 and v 2 . Let j ≥ 0 be the minimum distinguishing index for agents' labels, i.e., ξ(ℓ(A 1 )) j = ξ(ℓ(A 2 )) j and ξ(ℓ(A 1 )) j ′ = ξ(ℓ(A 2 )) j ′ for each 1 ≤ j ′ < j. Such an index j exists because the labels of the agents are different and hence the extended labels have a distinguishing index. Moreover,

Indeed, if the two labels are of the same length, then the extended labels are of the same length. If, on the other hand, the labels have different lengths, then the terminating bits are at different positions, which in particular implies that the terminating bit of the smaller label is at position that is distinguishing for the two extended labels.

By assumption, Observation 1 and an inductive argument, A i is at v i at the beginning of the j ′ -th call to procedure BoundDegrees during the execution of procedure CompareLabels, where