Chantal Thibert

Joanna Fombonne Apoptosis

Dependence receptors : Mechanisms of an Announced Death

Dependence receptors form a family of functionally related receptors which are all able to induce two completely opposite intracellular signals depending on the availability of their ligand. Indeed, in its presence, they mediate a positive, classical signal transduction of survival, differentiation or migration but without it, they trigger a negative signal which leads to cell death. The molecular mechanisms involved in triggering cell death in the absence of ligand are starting to be unravelled: dependence receptors are recruited at well-defined domains at the plasma membrane, they trigger cell death through a monomeric form, they are cleaved by caspases and they recruit a caspase activating complex.

Introduction

Receptors are usually considered to be inactive in the absence of their ligand. This generally accepted idea has been shown to be untrue for a family of unconventional receptors. Indeed certain receptors trigger "positive" signaling on survival, differentiation, and migration in the presence of their ligands, while they transduce a "negative" signal of cell death induction in the absence of their ligands (Fig. 1). Thus, cells expressing these receptors are in a state of dependence on their respective ligands and that is why these receptors have been named "dependence receptors". To date, 15 receptors have been shown to display these two opposite activities : p75 NTR , DCC, Neogenin, UNC5H receptors family, Androgen Receptor, Patched, RET, MET, TrkC, ALK, EphB4. These receptors are all involved both in embryonic development and in the regulation of tumor progression (for a full review, see 1

). One hypothesis is that the coexistence of these two signaling pathways (a positive one for migration, differentiation and a negative one for death) is probably crucial for the proper control of development processes (e.g. neural tube formation, …) and represents a safeguard mechanism to limit tumor expansion (see for reviews [START_REF] Mehlen | Dependence receptors: a new paradigm in cell signaling and cancer therapy[END_REF][START_REF] Mehlen | Metastasis: a question of life or death[END_REF][START_REF] Mehlen | Netrin-1 and its dependence receptors as original targets for cancer therapy[END_REF] ). Several recent reports have described the molecular mechanisms of death induced by some of the dependence receptors in the absence of their ligands. So far, these mechanisms appear to require the localization in lipid rafts and monomerization of the receptors. Furthermore, dependence receptors can both activate caspases (by recruiting a caspase-activating complex) and be their substrates. We will review here the current knowledge on how dependence receptors could trigger apoptosis.

The dependence receptors here discussed are p75 NTR (a receptor for NGF), DCC (Deleted in Colorectal Cancer) and UNC5H, (both are netrin-1 receptors), the Androgen receptor (AR), Patched (Ptc, the receptor of Sonic hedgehog Shh), integrins, Neogenin (a close homologue of DCC, receptor for RGM) and several tyrosine kinase receptors RET (REarranged during Transfection), MET, ALK, TrkC, EphA4, (receptors for GDNF, HGF/SF, pleiotrophin/midkine, BDNF and EphB3 respectively) (for a detailed description of dependence receptors and their ligands, see [START_REF] Mehlen | Dependence receptors: a new paradigm in cell signaling and cancer therapy[END_REF] ).

Localization in lipid rafts

Lipid rafts are dynamic membrane domains, rich in cholesterol and sphingolipids and characterized by their resistance to solubilization by mild detergents such as Triton X-100 [START_REF] Lajoie | Lattices, rafts, and scaffolds: domain regulation of receptor signaling at the plasma membrane[END_REF] . These subdomains of the plasma membrane are involved in clustering macromolecules. It has been proposed that lipid rafts serve as signaling platforms allowing binding/coupling between different molecules such as receptors with adaptors or effectors of signaling pathways such as kinases. Several studies report association of dependence receptors with lipid rafts, either to control the positive pathway (e.g., cell survival and thus differentiation), or to control the negative signaling pathway (cell death) (Fig 2). Concerning cell death induction, the dependence receptor localization to lipid rafts has been shown for DCC in both immortalized cells and primary neurons [START_REF] Furne | The dependence receptor DCC requires lipid raft localization for cell death signaling[END_REF] and for UNC5H2 [START_REF] Maisse | Lipid raft localization and palmitoylation: identification of two requirements for cell death induction by the tumor suppressors UNC5H[END_REF] . Indeed, after disruption of lipid rafts, (e.g., by cholesterol depletion), dependence receptors lose their ability to interact with proteins involved in the death signaling pathway, such as caspase-9 for DCC, or DAPK for UNC5H2 and thus their proapoptotic activity.

The mechanisms regulating receptor localization to lipid rafts are still unclear.

For instance, DCC needs to be palmitoylated to translocate into lipid rafts 7 5 .

Palmitoylation of the p75 NTR receptor has also been described [START_REF] Barker | The low affinity neurotrophin receptor, p75LNTR, is palmitoylated by thioester formation through cysteine 279[END_REF] and seems to reduce the receptor association with lipid rafts [START_REF] Bilderback | Association of p75(NTR) with caveolin and localization of neurotrophin-induced sphingomyelin hydrolysis to caveolae[END_REF] , although conclusive evidence supporting these findings is yet to be provided. However, p75 NTR phosphorylation by PKA is a step required to allow accumulation of p75 NTR in lipid rafts [START_REF] Higuchi | PKA phosphorylates the p75 receptor and regulates its localization to lipid rafts[END_REF] . UNC5H2 palmitoylation is required for its proapoptotic activity but not for its lipid rafts localization [START_REF] Maisse | Lipid raft localization and palmitoylation: identification of two requirements for cell death induction by the tumor suppressors UNC5H[END_REF] .

The presence of the ligand has been shown to be important for some dependence receptors to be integrated within lipid rafts. Indeed both p75 NTR and RET massively relocate within rafts after ligand binding 10 11 and at least in RET case, this represents a necessary step to control cell survival. However, this does not apply to the dependence receptors DCC and UNC5H2 whose localization on lipid rafts appears to be ligand independent 7 12 6 Lipid raft localization is thus crucial for the proapoptotic activity of some of the dependence receptors. Of note, clustering of the dependence receptor integrins has also been observed at the surface of dying cells [START_REF] Stupack | Apoptosis of adherent cells by recruitment of caspase-8 to unligated integrins[END_REF] , suggesting a possible localization of integrins in membrane subdomains. Moreover, Ptc has been described in specific membrane subdomains called caveolae, corresponding to nonclathrin coated invaginations [START_REF] Karpen | The sonic hedgehog receptor patched associates with caveolin-1 in cholesterol-rich microdomains of the plasma membrane[END_REF] . Moreover, Ptc ligand Hedgehog also localizes to lipid rafts in Drosophila [START_REF] Rietveld | Association of sterol-and glycosylphosphatidylinositol-linked proteins with Drosophila raft lipid microdomains[END_REF] . This is in line with previous results obtained with DCC, p75 NTR , RET and Met demonstrating that the localization to lipid rafts is not restricted to death signaling. Thus, dependence receptors requirement to localize to lipid rafts before triggering cell death could be a conserved mechanism.

Monomerization of dependence receptors

It has recently been shown that dependence receptor monomerization is a critical step for their pro-apoptotic activity, with multimerization being inhibitory for cell death (Fig 2). Indeed, the proapoptotic effect of p75 NTR may be blocked by the addition of dimeric neurotrophins [START_REF] Cortazzo | Nerve growth factor (NGF)mediated protection of neural crest cells from antimitotic agent-induced apoptosis: the role of the low-affinity NGF receptor[END_REF] or dimeric NGF-derived peptides [START_REF] Longo | Synthetic NGF peptide derivatives prevent neuronal death via a p75 receptor-dependent mechanism[END_REF] but not monomeric NGF-derived peptides [START_REF] Longo | Synthetic NGF peptide derivatives prevent neuronal death via a p75 receptor-dependent mechanism[END_REF] , suggesting that p75 NTR -induced apoptosis requires the monomeric form of the receptor. Using an artificial system of dimerization, Wang et al., have shown that monomeric p75 NTR is indeed required for apoptosis induction whereas dimerization and higher orders of oligomerization block this effect [START_REF] Wang | Dimerization-dependent block of the proapoptotic effect of p75(NTR)[END_REF] . The authors identified the last 19 amino-acids at the carboxy-terminus as the region required for the receptor dimerization. However, Rabizadeh et al showed that the deletion of these 19 aminoacids did not abolish the receptor proapoptotic activity and defined an extended sequence of 29 amino-acids at the carboxy-terminus (stretching from amino-acids 349 to 377) as the domain mediating the proapoptotic activity of p75 NTR 19 .

DCC has also been shown to homomultimerize in the presence of netrin-1, an important feature for the positive signaling of the receptor during axon guidance [START_REF] Stein | Binding of DCC by netrin-1 to mediate axon guidance independent of adenosine A2B receptor activation[END_REF] . Two domains were found to be involved in DCC oligomerization: one is the extracellular domain which aggregates upon netrin-1 binding ; the second one is in the cytoplasmic domain (C-Terminal part of the receptor named P3) which is responsible for selfassociation leading to constitutive multimerization independently of netrin-1 binding [START_REF] Stein | Binding of DCC by netrin-1 to mediate axon guidance independent of adenosine A2B receptor activation[END_REF] .

The authors conclude that the cytoplasmic domain of DCC is able to oligomerize constitutively but that this association is normally inhibited in the full-length receptor.

The hypothesis is that netrin-1 stimulates the formation of a receptor complex through association of the extracellular domains, then inducing a conformational change allowing DCC cytoplasmic domain multimerization. Knowing that DCC is able to oligomerize following netrin-1 binding, we investigated whether netrin-1-induced DCC and/or UNC5H2 multimerization is a critical step for DCC and/or UNC5H-mediated proapoptotic activity. We recently showed that DCC and/or UNC5H2 multimerize in response to netrin-1, and that this event is sufficient to inhibit apoptosis [START_REF] Mille | Interfering with multimerization of netrin-1 receptors triggers tumor cell death[END_REF] . We also demonstrated that a domain of DCC, DCC-5Fbn, that triggers cell death in vitro and tumor regression in animal models 22 23 does so by interfering with netrin-1-induced multimerization of DCC and/or UNC5H2 [START_REF] Mille | Interfering with multimerization of netrin-1 receptors triggers tumor cell death[END_REF] .

Other dependence receptors that have been shown to oligomerize in the presence of their ligand include all tyrosine kinase receptors: RET, TrkC, MET, ALK, EphB4 (for a review see [START_REF] Weiss | Switching signals on or off by receptor dimerization[END_REF] ) and also Ptc [START_REF] Lu | The C-terminal tail of the Hedgehog receptor Patched regulates both localization and turnover[END_REF] . Interestingly, several data had long suggested that Ptc could act as a multisubunit protein. First, Ptc is a multipass membran protein structurally similar to a RND family of channels and transporters (such as NPC1), several of which are known to have an oligomeric structure [START_REF] Kuwabara | The sterol-sensing domain: multiple families, a unique role?[END_REF] . Second, interallelic complementation has been observed during genetic analyses of Drosophila ptc suggesting direct interaction between partially impaired subunits [START_REF] Torroja | Patched controls the Hedgehog gradient by endocytosis in a dynamin-dependent manner, but this internalization does not play a major role in signal transduction[END_REF] . Third, Lu et al.

recently showed that Drosophila Ptc is able to multimerize [START_REF] Lu | The C-terminal tail of the Hedgehog receptor Patched regulates both localization and turnover[END_REF] . Indeed, they demonstrated that the last intracellular domain (the C-Terminal domain = CTD; Ptc is a multipass membrane protein) is able to trimerize by self-association. However, similarly to DCC [START_REF] Stein | Hierarchical organization of guidance receptors: silencing of netrin attraction by slit through a Robo/DCC receptor complex[END_REF] , Ptc is able to trimerize even if deleted of CTD [START_REF] Lu | The C-terminal tail of the Hedgehog receptor Patched regulates both localization and turnover[END_REF] . The process of oligomerization is essential to Ptc survival-inducing function and regulates its turnover in part via binding to Nedd4, an E3 ubiquitin ligase which could target Ptc to lysosomal degradation [START_REF] Lu | The C-terminal tail of the Hedgehog receptor Patched regulates both localization and turnover[END_REF] .

So far, the importance of the oligomerization in blocking proapoptotic activity has been proved for the receptors p75 NTR , DCC and Unc5H2. Experiments on other dependence receptors forced to oligomerize will help to understand whether the proapoptotic activity of this entire class of receptors depends on their ability to be on a monomeric state.

Recruitment of a caspase activating complex

Dependence receptors are able to activate initiator and effector caspases in the absence of their ligand (for a review, see [START_REF] Bredesen | Receptors that mediate cellular dependence[END_REF] ) (Fig 2). DCC [START_REF] Forcet | The dependence receptor DCC (deleted in colorectal cancer) defines an alternative mechanism for caspase activation[END_REF] , TrkC [START_REF] Tauszig-Delamasure | The TrkC receptor induces apoptosis when the dependence receptor notion meets the neurotrophin paradigm[END_REF] and Ptc 32 activate caspase-9 and -3, while integrin-induced death depends on caspase-8 and -3 activation 13 . The death of sympathetic neurons deprived of NGF is mediated by p75 NTR via the recruitment of caspase-2 [START_REF] Troy | Caspase-2 mediates neuronal cell death induced by beta-amyloid[END_REF] . The deletion of caspase-2, however, does not rescue neurons deprived of NGF because of the activation of an alternative pathway dependent on caspase-9 [START_REF] Troy | Death in the balance: alternative participation of the caspase-2 and -9 pathways in neuronal death induced by nerve growth factor deprivation[END_REF] . Along a similar line, GDNF-deprived neurons die by caspase-2 and -7 activation [START_REF] Yu | GDNFdeprived sympathetic neurons die via a novel nonmitochondrial pathway[END_REF] . Finally, the initiator caspases activated by the recently described dependence receptors such as ALK, MET, EphA4 still remain to be identified.

Several proapoptotic partners of dependence receptors have been identified (Table 1), but so far none of them emerge as a universal proapoptotic adaptor for dependence receptor-induced death.

DIP13α, a candidate partner of DCC identified by a two-hybrid screen, has been characterized as a mediator of DCC-induced cell death [START_REF] Liu | Mediation of the DCC apoptotic signal by DIP13 alpha[END_REF] . Interestingly, the domain that allows DCC to interact with DIP13α closely resembles the domain that is responsible for DCC proapoptotic activity [START_REF] Mehlen | The DCC gene product induces apoptosis by a mechanism requiring receptor proteolysis[END_REF] . Indeed, the overexpression of DIP13α enhances DCCinduced cell death, while its down regulation promotes survival [START_REF] Liu | Mediation of the DCC apoptotic signal by DIP13 alpha[END_REF] . It remains to be elucidated how DIP13α is linked link to caspase activation. DCC triggers caspase activation directly and in particular it interacts directly with caspase-3 and indirectly with caspase-9 [START_REF] Forcet | The dependence receptor DCC (deleted in colorectal cancer) defines an alternative mechanism for caspase activation[END_REF] . Furthermore, the DCC intracellular domain is able to activate caspase-3 in a cell free system, suggesting that DCC interacts through an adaptor protein with caspase-9, allowing caspase-3 activation. It is thus tempting to speculate that DIP13α is the missing link between DCC and caspase-9. NRAGE, a member of the MAGE family, is known to interact with UNC5H1 in the ZU-5 domain [START_REF] Williams | UNC5H1 induces apoptosis via its juxtamembrane region through an interaction with NRAGE[END_REF] . This region of UNC5H1 (with an adjacent PEST sequence) is required for UNC5H1-mediated apoptosis, which is prevented in a model of down-regulation of NRAGE.

DAPK (for death-associated protein kinase) was identified as the proapoptotic partner of the dependence receptor UNC5H2 [START_REF] Llambi | The dependence receptor UNC5H2 mediates apoptosis through DAP-kinase[END_REF] . DAPK is a crucial protein mediating cell death induction via its serine/threonine kinase activity and via its death domain. This protein was first identified in an in silico search as the one having the death domain closest to that of UNC5H2. Llambi et al (2005) showed that DAPK is required for a large part of UNC5H2-induced apoptosis and that UNC5H2 triggers cell death by activating DAPK in the absence of its ligand, netrin-1. More recently, DAPK has also been shown to be involved in the death process induced by another dependence receptor, Neogenin, which is not structurally related to the UNC5H2 receptor [START_REF] Fujita | Neogenin regulates neuronal survival through DAP kinase[END_REF] . Indeed, Neogenin lacks a death domain but contains domains of high homology to DCC in its extracellular part and domains of less extended homology to DCC in its cytoplasmic part. However, DAPK is not an interactor of DCC [START_REF] Fujita | Neogenin regulates neuronal survival through DAP kinase[END_REF] . These data suggest that even if DAPK is involved in death signaling induced by several dependence receptors, the mechanisms of DAPK recruitment by the single receptors are different from one another. However, at the functional level, the role of DAPK in dependence receptors induced cell death is similar to that of UNC5H2 and Neogenin. Indeed, the DAPK kinase activity of is evident only in the absence of ligands.

For the RET dependence receptor, another death signaling pathway has been described in somatotrophic cells, the pituitary cells deputed to secrete growth hormones. In the absence of RET's ligand GDNF, the intracellular part of RET forms a complex with caspase-3 and PKCδ in which all three proteins become activated by cleavage [START_REF] Canibano | The dependence receptor Ret induces apoptosis in somatotrophs through a Pit-1/p53 pathway, preventing tumor growth[END_REF] . This activated complex leads to binding of c/EBPα to the promoter of Pit-1, a pituitary specific transcription factor depending on JNK and CREB signaling. The upregulation of Pit-1 expression then leads to increased p53 expression and apoptosis.

Importantly, in vivo observations showing larger adenopituitary glands in knock-out RET animals strengthened the in vitro data.

Recent data from our laboratory shown that, in the absence of its ligand, Ptc interacts with the adaptor protein DRAL/FHL2 to trigger cell death. DRAL was identified by a two-hybrid screen taimed at finding proteins involved in cell death control that would interact with the propaoptotic domain of Ptc (i.e., its 7th intracellular domain). We demonstrated that, in the absence of Shh, Ptc actually recruits a protein complex that includes DRAL, one of the caspase recruitment domain-CARD containing proteins TUCAN or NALP1, and the apical caspase-9 [START_REF] Mille | The Patched dependence receptor triggers apoptosis through a DRALcaspase-9 complex[END_REF] . All these proteins were identified as the partners required by Ptc to induce apoptosis both in immortalized cells and during neural tube development in chick embryos. Moreover, Ptc triggers caspase-9 activation and enhances cell death through a caspase-9-dependent mechanism. In view of these findings, we proposed that in the absence of its ligand Shh, the dependence receptor Ptc serves as the anchor for a caspase-activating complex that includes DRAL and caspase-9.

In summary, no proapoptotic partners common to all dependence receptors have been so far characterized. Future studies should tell us if each dependence receptor triggers cell death by means of a unique signaling pathway or if a common proapoptotic effector indeed exists. However, as shown for DCC and UNC5H2 5 6 the interaction of dependence receptors with their proapoptotic partners seems to require their localization to lipid rafts. Indeed, when a mutant of receptor palmitoylation is used or when the lipid rafts organization is perturbed, no interaction with the proapoptotic partner was observed. Similarly, clustering of integrins results in caspase-8 recruitment [START_REF] Stupack | Apoptosis of adherent cells by recruitment of caspase-8 to unligated integrins[END_REF] suggesting the necessity to group dependence receptors in a restricted domain at the membrane before the caspase-activating complex can be recruited.

Cleavage of dependence receptors by caspases

In the absence of their ligand, dependence receptors can be cleaved by caspases. This has been shown in vitro for most dependence receptors with the exception of integrins and p75 NTR which is processed proteolytically by an unknown protease [START_REF] Kanning | Proteolytic processing of the p75 neurotrophin receptor and two homologs generates Cterminal fragments with signaling capability[END_REF] . p75 NTR , however, can be cleaved in vitro by caspases but it is still unclear whether this cleavage is required for p75 NTR proapoptotic activity (S. Rabizadeh, personal communication).

The caspase found to be responsible for the cleavage of most dependence receptors in vitro is caspase-3. This finding, of course, does not exclude the requirement of other caspases in vivo. The cleavage sites of caspases have been mapped (Table 1) and their mutations abolish the proapoptotic activity of the corresponding dependence receptor, suggesting that the cleavage of these receptors is required to promote apoptosis. Dependence receptors can be classed in two categories depending on the number and position of caspase cleavage sites. In the presence of one cleavage site located upstream of the proapoptotic domain, the proapoptotic activity of the receptor is anchored to the plasma membrane. The caspase cleavage then allows for the exposure of a proapoptotic domain which is normally masked by the C-terminal domain of the receptor. This mechanism has been described for DCC, Ptc, Neogenin, ALK and EphA4. In the other hand, in the presence of two caspase cleavage sites, an intracellular fragment containing the proapoptotic activity of the receptor is then released from the membrane to the cytoplasm; this seems to occur for RET, MET and TrkC. Futhermore, it was shown that the cleavage of MET occurs in a sequential manner, with the site located at the C-Terminal region promoting a cleavage at the juxtamembrane region of the protein [START_REF] Foveau | Amplification of apoptosis through sequential caspase cleavage of the MET tyrosine kinase receptor[END_REF] . The C-terminal cleavage generates a fragment of the last 5 amino acids of MET which is undetectable. However, Foveau et al. studied this cleavage thanks to a tagged version of the receptor having a V5 epitope at its carboxyterminus [START_REF] Foveau | Amplification of apoptosis through sequential caspase cleavage of the MET tyrosine kinase receptor[END_REF] .

Although not yet demonstrated, a cryptic cleavage site might also exist for other dependence receptors.

However the cleavage occurs, it is generally thought that it induces a conformational change of the dependence receptor, then allowing the exposition/release of an addiction/dependence domain (ADD) responsible for triggering cell death.

Cleavage of dependence receptors has been observed in cellulo for AR [START_REF] Ellerby | Kennedy's disease: caspase cleavage of the androgen receptor is a crucial event in cytotoxicity[END_REF] and all the receptors belonging to the Receptor Tyrosine Kinase family : RET [START_REF] Bordeaux | The RET proto-oncogene induces apoptosis: a novel mechanism for Hirschsprung disease[END_REF] , MET [START_REF] Tulasne | Proapoptotic function of the MET tyrosine kinase receptor through caspase cleavage[END_REF] , ALK [START_REF] Mourali | Anaplastic lymphoma kinase is a dependence receptor whose proapoptotic functions are activated by caspase cleavage[END_REF] , TrkC 31 and EphA4 [START_REF] Furne | EphrinB3 is an anti-apoptotic ligand that inhibits the dependence receptor functions of EphA4 receptors during adult neurogenesis[END_REF] . Such a cleavage still remains to be observed in cellulo or in vivo for other dependence receptors in order to better understand its biological meaning. The receptor need to be cleaved before exerting their proapoptotic activity raises the question as to wether they can be considered promoters of apoptosis rather than a mere substrate of caspases already activated by other stimuli. This apparent contradiction could be explained by the notion that caspases are not completely dormant in non-apoptotic cells, but possess a residual activity [START_REF] Salvesen | Caspases: intracellular signaling by proteolysis[END_REF] ; [START_REF] Yang | Autoproteolytic activation of pro-caspases by oligomerization[END_REF] ; thus the receptors could be cleaved by little active caspase zymogens. Indeed, local activation, not resulting in cell death, has been documented in several systems ( 50 ; for a review see [START_REF] Abraham | Death without caspases, caspases without death[END_REF] suggesting that apoptosis could be a consequence of the amplification rather than of the initiation of caspase activity (Fig 2). It is possible that dependence receptors trigger cell death after ligand withdrawal by first recruiting a caspase-activating complex; activated initiator caspases could then cleave and thus activate effector caspases. These caspases would then cleave dependence receptors, induce a change of conformation, expose/release the ADD then recruiting more caspase-activating complex or other partners in order to trigger more caspase activation. The cleavage of dependence receptors could thus represents a threshold of caspase activation beyond which apoptosis is unleashed. However, we cannot dismiss the alternative possibility that caspase cleavage is a necessary step that will allow the interaction with the caspaseactivating complex. Along this line, it was shown that DCC interaction with caspase-9 occurs only when the receptor is cleaved and is not observed when DCC is mutated in its caspase cleavage site [START_REF] Forcet | The dependence receptor DCC (deleted in colorectal cancer) defines an alternative mechanism for caspase activation[END_REF] . The development of new tools, including specific antibodies raised against cleaved dependence receptors, should help to determine the precise sequence of events leading to an irreversible cell demise.

Conclusions

Recent studies have highlighted a number of the molecular mechanisms by which dependence receptors initiate cell death in the absence of their ligands. This death pathway is only activated when dependence receptors localize to lipid rafts and are in a monomeric state. Ligand-free dependence receptors could recruit a caspase-activating signal mediated by means of adpator molecules acting as linking agents. The activated initiator caspase (mainly caspase-9 but sometimes caspase-8) could then activate effector caspases such as caspase-3. Whether this recruitment and the ensuing caspase activation occur before or after the cleavage of these receptors by active caspases, a necessary step toward the amplification of their caspase activity, remains to be seen.

Figure and Table Legends Table 1: Summary of known death adaptors of dependence receptors, caspases involved and caspase cleavage sites

The fourth steps discussed in the text are highlight in this table. Lipid raft association of the dependence receptors-induced cell death is noticed. Monomerization of the receptor as a crucial step to trigger cell death upon ligand removal is mentioned. The state-ofthe-art about the existence of a caspase-activating complex is broken down in (i) the known proapoptotic partner recruited, (ii) the caspase involved and (iii) the eventually description of cytochome c release associated with dependence receptor-cell death in order to characterized a mitochondrial death pathway. Caspase cleavage sites are indicated. * : reported in cellulo cleavage. ND : not determined. It is usually said that receptors function only in response to ligand binding. However, dependence receptors are not inactive in the absence of ligand, but rather display two opposing signaling properties: in the presence of ligands, they induce a positive signal of survival and then differentiation or migration; in their absence, they trigger apoptosis. Thus, the survival of cells expressing such dependence receptors depends on ligand availability. In the absence of a ligand, dependence receptors may trigger apoptosis if receptors are localized into lipid rafts, are in a monomeric state and the recruitment of a complex leading to caspases activation and cleavage of the receptor by caspases that enhances the cell death signal.

  Tools to detect cleaved receptors in vivo are under development and their use should shed new light on this cleavage step.

Figure 1 :

 1 Figure 1: Dependence receptors as two-sided receptors.

Figure 2 :

 2 Figure 2: Hypothetical model of dependence receptors-induced apoptosis.

Table 1 -

 1

			Caspase-activating complex
	Survival	Dependence	Proapoptotic	Initiator caspase	Dependence
	inducing	Receptor	partners	involved	receptor caspase
	ligand				cleavage site
	NGF	P75	NRAGE ?	caspase-2 ?	Uncharacterized
	netrin-1	DCC	DIP13-α	caspase-9	D1290
	netrin-1	UNC5H1	NRAGE	ND	ND
	netrin-1	UNC5H2	DAPK	not caspase-8	D412
	RGM	Neogenin	DAPK	ND	D1323
	androgen	AR	ND	ND	D146 and around
					D660
	EML (ex :	Integrin	ND	caspase-8	No cleavage
	laminin)
	Shh	Patched	DRAL/FHL2,	caspase-9	D1392
		Ptc	TUCAN/NALP1
	GDNF	RET	Pit1/P53	caspase-2 ?	D707, D1017
	HGF/SF	MET	ND	ND	D1000, D1374
	Pleiotrophin/	ALK	ND	ND	D1160
	midkine
	NT3	TrkC	ND	caspase-9	D495, D641
	EphB3	EphA4	ND	ND	D773/774

Acknowledgments:

We are really grateful for S. Vesce and F. Hemming for critical reading of the manuscript and text correction. The work in Mehlen's laboratory is supported by the Ligue Contre le Cancer, the Centre National de la Recherche Scientifique, the ANR and the INCA. J. F. is supported by an ARC fellowship.

Survival


Prithwish Basu
email: pbasu@bbn.com

Saikat Guha
email: sguha@bbn.com

Effect of Limited Topology Knowledge on Opportunistic Forwarding in Ad Hoc Wireless Networks

Opportunistic forwarding is a simple scheme for packet routing in ad hoc wireless networks such as duty cycling sensor networks in which reducing energy consumption is a principal goal. While it is simple and can be analytically characterized, it suffers from a high end-to-end latency. In this paper we show how this latency can be drastically reduced if nodes have limited knowledge of network topology (that can be achieved by scoped dissemination of link state information), and hence deriving a hybrid routing protocol. We give an analytical formulation of end-to-end latency between any pair of nodes in such duty cycling networks as the scope of topology dissemination is varied. We borrow from our prior results derived from spectral graph theory to derive exact expressions for mean latency as a function of various network and protocol parameters such as size, duty cycle probability, and scope of link state dissemination. These analytical expressions agree very well with simulation results. We also show how this latency analysis can be coupled with overhead analysis to determine good values of topology dissemination scope.

I. INTRODUCTION

Routing in wireless multihop networks has been a topic of intense research for the past several decades. The space of requirements in multihop networking is so diverse that no single protocol outperforms the rest in all different scenarios that are characterized by attributes such as network size (small vs. large or dense vs. sparse), link dynamics (deterministic vs. stochastic), mobility patterns (regular vs. irregular/random), traffic patterns (local vs. global), traffic load (low vs. high), optimization metrics (shortest path vs. lowest latency vs. lowest energy consumption) etc. Most researchers use simulation as the primary means of conducting performance evaluation of these protocols. While the complexity of protocols amply justifies realistic simulation and real implementation and deployment of protocols, this has resulted in a general lack of rigor in the literature in the analysis of the fundamental properties of these protocols.

This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence and was accomplished under Agreement Number W911NF-06-3-0001. The views and conclusions contained in this document are those of the author(s) and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.

Analytical frameworks, albeit simplistic, can give deeper insights into the fundamental properties of protocols than simulations or real implementations, hence we propose some analytical techniques to study a simple class of routing protocols in this paper and show how effective such techniques can be to study a fundamental property of routing protocolspath length or latency. The specific class of protocols that we study in this paper is that of opportunistic forwarding in duty cycling networks.

Duty cycling (or sleep-scheduling) in energy-constrained wireless ad hoc networks refers to the process of turning radio transceivers OFF for conserving battery energy that is wasted by idle listening, and then turning them back ON when there is an opportunity to participate in network communication. Several mechanisms have been proposed in the literature for performing duty cycling [START_REF] Ye | Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks[END_REF], [START_REF] Lu | Delay Efficient Sleep Scheduling in Wireless Sensor Networks[END_REF], [START_REF] Redi | JAVeLEN: An Ultra-Low Energy Ad hoc Wireless Network[END_REF]. In the pseudo-random duty cycling model [START_REF] Redi | JAVeLEN: An Ultra-Low Energy Ad hoc Wireless Network[END_REF], by exchanging a small set of parameter values (such as seed and cycle position of a pseudo-randomnumber-generator, and wake-up probability p), each node can construct the exact ON/OFF state information of its neighbors, thus allowing for energy-efficient communication.

In energy-constrained networks with time-varying topology caused by duty cycling, it is often difficult to execute traditional MANET routing protocols because disseminating/gathering topology state from the entire network is a time and energy consuming expenditure. Moreover, at low duty cycling probabilities, dissemination of topology information (a step used by the link-state family of schemes) or that of route queries and responses (steps used by reactive protocols) can take a significant amount of time which can render the topology information less useful by the time it is gathered. Hence stateless opportunistic forwarding (e.g. forward the packet to the first neighbor that would wake up, or first-contact routing in DTN scenarios) is a simple technique which can be used to deliver packets under such resource constrained scenarios [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF]. However, a significant drawback of this scheme is the high end-to-end latency suffered due to the random walk component.

Clearly, a natural mechanism for improving the latency performance of this routing scheme is to utilize some topology information for routing. In this paper, we study two such scenarios: (a) what is the effect of routing topology knowledge on the latency of opportunistic forwarding in two-dimensional grid lattices (with Manhattan routing); and (b) what is the effect of partial knowledge of routing topology on latency of opportunistic forwarding in general network topologies, i.e. when nodes limit their link state topology dissemination to k hops?

Our contributions in this paper are the following: 1) Exact expressions for expected latency of random walks as a function of the size of the grid n, and the duty cycling probability p. 2) Analytical expression for expected latency of random walks in the regular line lattice with k-hop topology information. 3) General expression for expected latency of random walks for any general network topology with k-hop topology information. This could help us choose a value of k that optimizes the overhead vs. latency tradeoff. 4) The analytical results mentioned above agree very well with simulations. To the best of our knowledge this is the first paper that analytically studies the dependence of scope k on the performance of random walks in wireless networks, with or without duty cycling. 5) We also determine good values of k by performing joint analysis of latency and overhead.

A. Organization of the rest of the paper

Section II analytically studies the latency of duty cycling random walks on 2-D grid lattices with Manhattan routing. Section III investigates analytically how the availability of limited amount of topology information affects the properties of a hybrid random-walk/link-state routing algorithm. Section IV describes simulation results and how they compare to the analytical results presented in the earlier sections. Section VI concludes the paper with a discussion on future research directions.

II. EFFECT OF TOPOLOGY KNOWLEDGE ON DUTY-CYLING RANDOM WALKS: MANHATTAN ROUTING SCENARIO

Before studying the effect of limited topology knowledge, we first study how opportunistic forwarding (in the form of a duty cycling random walk [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF]) performs in the presence of topology knowledge in a simple yet non-trivial topology.

In particular, we study the Manhattan grid scenario where a packet can only be forwarded to an awake neighbor located in the north or east direction.

Consider a lattice of (n + 1) × (n + 1) nodes labeled from (0, 0) to (n, n). The length of all shortest Manhattan paths from the south-west corner to the north-east corner is 2n. However, different paths could have different latencies since there may be a different number of neighbors that are available for forwarding at specific locations in each of the paths. For example, Figure 1 illustrates that once the path hits either the easternmost column or the northernmost row, each segment only allows one choice for forwarding, whereas there are 2 choices for forwarding at all other locations. We compute the expected latency incurred along a path of length 2n on this In segments where only one choice is available for forwarding, the expected waiting latency in slots is given by E[W ] = 1 p (since the latency random variable obeys the Geometric distribution). In segments where 2 choices are available for forwarding, the computation of the expected latency is a little more complicated. If the waiting time for each of the two choices is modeled as two i.i.d. discrete random variables X and Y , then the resultant random variable for waiting time is Z = min(X, Y ). Since X and Y are geometrically distributed with parameter p, then Z is also geometrically distributed with parameter 1 -(1p) 2 . Hence the mean waiting time in the segments of 2 choices is given by E

[W ] = 1 1-(1-p) 2 .
Now we compute how many segments in each path of length 2n are of each of the above two categories. A well known result indicates that the number of paths on a 2D lattice from point (0, 0) to (a, b) is given by a+b b . Hence the number of paths from (0, 0) to (n, n) is 2n n which is (n + 1)C n where C n is the n th Catalan number. Now half of these paths enter the northernmost row from the south, i.e, at some (k, n), k ∈ [0, n -1], and the other half enter the easternmost row from the west, i.e., at some (n, k), k ∈ [0, n -1]. A path that enters (k, n) from (k, n -1) has nk segments with one choice and n + k segments of 2 choices, and there are n+k-1 k such paths. This is because this quantity is equal to the number of paths from (0, 0) to (k, n -1). Similarly there are n+k-1 k paths that enter (n, k) from (n -1, k).

Observe that all Manhattan paths from (0, 0) to (n, n) are not equiprobable. This is intuitively clear since a path that follows the edge of a grid has an equal number of 2-choice vertices and 1-choice vertices; on the other hand, a path that mostly passes through the core of the grid has many more 2-choice vertices than 1-choice vertices. Once a path hits a 1-choice vertex, its fate is sealed and it has no more choices until it reaches the destination. As mentioned earlier, a path that enters (k, n) from (k, n -1) has nk 1-choice vertices and n + k 2-choice vertices; therefore the probability of being on this particular path is given by p k = 1 2 n+k . If we consider paths hitting both the north boundary and the east boundary of the grid, the number of such paths is given by m n,k = 2 n+k-1 k . We can easily verify that the probabilities all add up to 1 since

n-1 k=0 p k m n,k = 1.
Therefore, the mean latency over all paths of length 2n is given by:

E[L(P 2n )] = n-1 k=0 1 2 n+k-1 n + k -1 k × n + k 1 -(1 -p) 2 + n -k p (1)
We use the following standard combinatorial identities to derive a closed form expression for Equation 1:

n-1 k=0 n + k 2 n+k-1 n + k -1 k = 2n - n 2 2n-1 2n n (2) n-1 k=0 n -k 2 n+k-1 n + k -1 k = n 2 2n-1 2n n (3)
Therefore, substitution of Equations 2 and 3 into Equation 1yields:

E[L(P 2n )] = 1 1 -(1 -p) 2 2n - n 2 2n-1 2n n + 1 p n 2 2n-1 2n n (4)
A quick sanity check indicates that as p → 0, E[L(P 2n )] → ∞ and for p = 1, E[L(P 2n )] = 2n which is expected. Figure 2 plots the latency expression in Equation 4 as a function of n and p. The linear behavior in n can be observed for a fixed value of p. However, for small values of p, the latency has a ∼ 1 p dependence. Figure 2 plots the latency expression in Equation 4as a function of n and p. The linear behavior in n can be observed for a fixed value of p. However, for small values of p, the latency has a ∼ 1 p dependence.

III. EFFECT OF PARTIAL TOPOLOGY KNOWLEDGE ON RANDOM WALKS

In this section we investigate the scenario where only a limited amount of topology information is available around the destination node. There are several reasons why this can happen:

1) Smart link state protocols such as Hazy Sighted Link State (HSLS) [START_REF] Santivanez | Making link-state routing scale for ad hoc networks[END_REF] disseminate the link state information more frequent to nearby nodes and less frequently to farther away nodes. HSLS performs this trick in order to reduce the control overhead 2) A destination node may decide to broadcast link state information (i.e. state of the links between itself and its neighboring nodes) only to nodes within a limited scope. It may do that for scalability reasons since frequent network wide broadcasts can cause severe congestion in the network due to broadcast storms (even in the HSLS scenario).

In the first case, a node located topologically far away from the destination typically does not have any routing information about the destination node, hence it needs to find the latter using mechanisms other than link state routing. In networks such as duty cycling sensor networks or disruption prone networks, opportunistic forwarding algorithms are useful since they require little or no state to make forwarding decisions. For example, a node can give the packet to the first neighbor that is supposed to wake up or the first neighbor with whom a link is established or reestablished. Latency of such algorithms have been studied before [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF], [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF] using techniques from spectral graph theory.

If each node X disseminates its own link state information to nodes within k hops, then nodes inside the k-hop neighborhood of X are able to route a packet to X along a minimum hop route of length k using this information. Since nodes outside the k-hop neighborhood of the destination may need to send a packet to the latter, we propose to use an opportunistic forwarding scheme (i.e. a random walk) until the packet reaches a node that is located within the k-hop neighborhood of the destination. This is a hybrid algorithm which we refer to as RANDWLS. Note that in this paper we do not formally claim that RANDWLS is optimal or near-optimal in terms of end-to-end latency for any protocol that admits k-hop topology knowledge and 1-hop knowledge of node-availability schedules. However, it is a simple effective protocol that can yield reasonable performance. Hence it is useful to study its performance analytically rather than just using simulations.

In this section we pose the following questions, and answer some of them positively:

1) If a node Z that is k > k hops away from X sends a packet via random walk, what is the estimated latency suffered by the packet until it hits a node that is in the k-hop neighborhood of X? (Obviously then the random walk terminates and a shortest path k-hop route is followed to reach X. 2) What is the dependence of network properties (size, structure etc.) and the scope of link state dissemination (i.e. value of k) on the latency of the aforementioned hybrid routing scheme? 3) What is the fundamental tradeoff between total overhead (link state dissemination and random data forwarding) and end-to-end latency of RANDWLS? We illustrate the effect of k-hop topology information on a random walk by an example in Figure 3(a). Node 40 wants to send a packet to node 14. In the absence of any link state topology dissemination, the random walk would have a propensity to "roam" in the upper half of the topology even after it reaches node 3. However, due to 2-hop dissemination of link state knowledge by node 14, as soon as the random walk reaches either node 5 or node 19, shortest path routing takes over, and thus significantly reduces the latency of the packet.

While the benefits of using limited topology information are intuitively obvious, an analytical characterization of the latency as a function of various network and protocol parameters is necessary to understand the underlying process better.

We first show how analysis is possible on a special topology (1-D line lattice) using elementary techniques and then proceed to more advanced techniques for handling general topologies. This analysis will be useful in determining the fundamental tradeoffs between short low-latency paths and control overhead (i.e. how far should the link state information be spread).

Note that although the hybrid protocol RANDWLS is by no means optimal, it is however very simple to implement and useful in disruption-prone scenarios where classic stateful protocols break down. This is not just true for proactive linkstate protocols -even reactive protocols like DSR and AODV do not work well in disruption-prone networks since stable contemporaneous end-to-end paths are not always present.

A. Random walk on line topology with partial knowledge

Let us consider a finite line lattice containing N nodes, numbered serially from 1 through N , such that 1 and N are the two terminal degree-1 nodes. When nodes never go to sleep (i.e. when p = 1, or no duty-cycling), the mean hitting time H m,n for a source-destination node pair {m, n} is the average number of time-slots a packet needs to traverse from node m to node n, when on each time slot the packet randomly moves to a one-hop adjacent node. The expression for H m,n is straightforward to derive using the Lovasz formula [START_REF] Lovasz | Random Walk on Graphs: A Survey[END_REF], and is given by: where 1 ≤ m ≤ n ≤ N . This result can be generalized to the case of opportunistic forwarding [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF] with pseudo-random duty-cycling with an average node-awake probability p, using our results in [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF]. The resulting hitting time expression is given by:

H m,n = (n -m)(m + n -2), (5)
H m,n = (n -m) 1 p + m + n -3 1 -(1 -p) 2 , ( 6
)
where 1 ≤ m ≤ n ≤ N , and 0 < p ≤ 1. 1 p and 1

(1-(1-p) 2 are waiting times (in number of slots) at a node of degree 1 and 2 respectively under pseudo-random duty cycling. Note that Eq. ( 6) reduces to Eq. ( 5) for p = 1. It is also worth noting that neither of Eqs. ( 5) or ( 6) are functions of N , because the random walk never goes to the "right" of the destination node n. With this observation, an alternative and more intuitive way to obtain the hitting-time expression in Eq. ( 6) is to solve the tridiagonal system of recursive equations given by:

H 1,n = 1 p + H 2,n , (7)
H 2,n = 1 p + 1 2 (H 1,n + H 3,n ) , (8)
. . .

H n-2,n = 1 p + 1 2 (H n-3,n + H n-1,n ) , ( 9
)
H n-1,n = 1 p + 1 2 H n-2,n , (10)
with the trivial condition, H k,k = 0, ∀k. For the explicit solution of the above recursion, see Appendix VII. Now let us consider the case as depicted in Fig. 4. Let us consider a hybrid routing scheme where a destination node n disseminates topology information to nodes located within its limited scope (k-hops, where k is a constant), and a source node m initiates a random walk until the packet finds any node that has received a topology update from the destination. Let us take a source-destination pair m, n with m < n. If m is within the k-hop boundary of n, i.e. nk ≤ m ≤ n (the shaded region in Fig. 4), then the mean hitting time H m,n = n-m p is just the length of the shortest path (nm) times the mean latency at each hop before the next neighbor along the shortest path comes awake, i.e., 1/p. If m is outside the k-hop boundary of the destination, i.e., m < nk, then the mean hitting time is obtained from Eq. ( 6) by replacing n with nk (the mean number of hops to hit the k-hop boundary node nk) plus k p , i.e.,

H m,n = k p + (n -k -m) 1 p + m + n -k -3 1 -(1 -p) 2 (11)
Using the symmetry condition to allow for m > n, i.e., H m,n = H N -m+1,N -n+1 , the mean hitting time can thus be represented in compact notation as follows:

H m,n = min(k, |n -m|) p + 1 p + (N -k -2) + (N + 1 -m -n)sgn(m -n) 1 -(1 -p) 2 × max(0, |n -m| -k), ( 12
)
where sgn(x) is the sign of x, and 1 ≤ {m, n} ≤ N . We plot in Fig. 5 the expression for hitting time as a function of m and n for k = 0, 10 and 20 for a N = 20 node line topology.

B. Random walk in general topologies with partial knowledge

We now analyze the performance of RANDWLS in a general network topology where nodes are dynamically duty cycling themselves with probability p, and each node disseminates topology link state information to within its k hop radius. In the pure opportunistic forwarding scenario (as we have considered in our prior work [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF], [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF]), the random walk does not terminate until it reaches a single node -i.e., the destination node. In general, the set of nodes located in the k-hop boundary of the destination can have cardinality greater than one. This can be observed from Figure 3(a). Therefore, a random walk has a finite probability of being terminated at more than one node after it leaves the source. This has the potential of significantly improving the overall latency performance of RANDWLS because the expected time to hit any of the k-hop neighborhood nodes is expected to be lower than the single node case.

We use techniques from spectral graph theory to study the latency on a general graph after performing the following operations on the original graph.

1) Let G = (V, E) be the original graph and s, d ∈ V be the source and destination nodes respectively. 2) Let Γ k d denote the nodes in the k-hop neighborhood of node d including the latter.

3) Let ∆ k d be the set of nodes in the k-hop boundary of d. , let E k u be the set of edges between u and the nodes in ∆ k d . Then the weights of these new edges is given by, w (u,t) = |E k u |. Figure 3(b) illustrates the above process when applied to the setup shown earlier in Figure 3(a). In this example t = 51 is the new terminal node and the blue edges are the new edges constructed between the k + 1-hop boundary of the original destination and node t. All older edges e still have weight w e = 1. It is easy to observe that after this construction, the mean latency of a simple random walk between node s and any node in the k-hop boundary of d is the same as the mean latency of a weighted random walk between s and t in the transformed graph G .

Clearly, ∆ k+1 d = Γ k+1 d \ Γ k d . Let E k = {e = (u, v)|e ∈ E, u ∈ ∆ k+1 d , v ∈ ∆ k d }. 4)
The mean latency between s and t can be computed using results from our prior work on spectral graph theory [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF]. Specifically, the hitting time of a weighted random walk between nodes u and v on G is given by, where w u,v is the weight assigned to edge (u, v) that dictates the probability that a random walk goes from u to v; this probability is given by ρ u,v wu,v wu ; w u v ∈Nu w u,v where N u is the neighborhood of u; u,v is the expected sojourn time for a packet to traverse an edge (u, v);

H u,v = k:σ k =0 W σ k µ 2 k,v w v v - µ k,u µ k,v √ w u u w v v (13)
u w∈Nu ρ u,w • u,w is the expected sojourn time at u; W (u,v)∈E w u,v ( u,v + v,u ) =
u ∈V w u u ; and σ k and µ k are the (k + 1)-th eigenvalue and the corresponding eigenvector of L, where L is the generalized Laplacian of G with edge weights and sojourn times. µ k,u is the u-th component of the eigenvector. The reader is directed to our prior work for a complete terminology and derivation [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF]. Finally, the expected end-to-end latency of RANDWLS from s to d in graph G can be computed by incorporating both random walk and shortest path components as follows:

E[L s→t (G)] = H s,t (G ) + k p (14)
While closed form expressions for hitting times do not exist for general graphs, Equation 14 is an exact calculation and is not an approximation. Computing hitting times takes O(|V | 3 ) running time due to the computation of the eigenvalues and eigenvectors but it is still an analytical means of computing latency performance in contrast with simulation based approaches. We however, do not undermine the power of simulation since certain realistic factors such as channel properties and protocol inefficiencies are more difficult to model analytically. In Section IV we discuss how our analytical results compare with simulations.

Note that a closed form expression is not difficult to derive for a special topology such as a line (as shown in Section III-A) or a ring. Random walk latency on a ring has a simple closed form expression [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF], and collapsing the k-hop neighborhood of a node by performing the operation proposed earlier preserves the ring topology; thus the same mathematics can be applied after replacing n with n-2k +1. However, this property does not hold for most other graphs, hence deriving a closed-form expression is more difficult.

IV. PERFORMANCE EVALUATION

In this section we evaluate the RANDWLS routing scheme as k and p are varied. In Fig. 5, we analytically plot latency performance in 1-D networks. For general topologies, we use the standard random geometric graph (RGG) model for wireless multihop scenarios which is represented by G(n, r) where n is the number of nodes in the graph whose coordinates are drawn from within a two-dimensional unit square, and r is the transmission radius of each node. There is a link between u and v if and only if their coordinates are less than or equal to r distance apart. Indeed, RGG is too simplistic a model for wireless multihop networks but we chose to use it because it is the simplest model that succinctly captures the spatial aspect of multihop wireless networks, and here it is our endeavor to understand the basic properties of RANDWLS under perfect communication channels. Performance under more sophisticated channel models is a topic of future research.

To verify the accuracy of the analytical expressions computed in this paper, we compare the results to analysis to results obtained from simulation of RANDWLS. The simulation was performed in a custom random-walk-on-graph simulator with perfect channel conditions and where one packet was sent between the farthest pair of source/destination nodes.

Figure 6 establishes the accuracy of the analytical expressions computed in Section III-B. We simulate a random walk on 100 different RGGs on 20 nodes at the critical radius of connectivity and for duty cycling probability p = 0.1. The critical radius of connectivity is given by [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF]: cr(n) ≈ log n πn For each instance of an RGG we plotted the latency in number of timeslots between the farthest sd pair. Both simulation and analysis results are plotted in the two plots on the left. The top left plot shows a scenario where 100 different random walks were simulated between the farthest sd pair for each of the 100 graphs, whereas the bottom left plot shows the case where 1000 random walks were simulated.

The plots on the right of Figure 6 indicate the deviation between the simulation and analytical results. We observe that simulation results agree closely with analysis and as we average over a greater number of simulation runs, the error reduces significantly, i.e. from mostly within 5% (when averaged over 100 random walks) to mostly within 2% (when averaged over 1000 random walks). The error goes down further when we average over an even larger number of random walks. We do not show results for other topologies such as grid but simulation and analysis agree very closely for those topologies as well.

In Figure 7, we study the latency of RANDWLS between the farthest sd pair in a 100 node RGG shown on the left. We can make two observations from the above results:

1) For each fixed value of k, we see that reducing p has some effect on latency reduction but the gains are marginal beyond a certain value of p. However, for sparser topologies such as grids, the latency curve does not flatten as rapidly with increasing p.

2) For each fixed value of p, we see a significant reduction in latency as k is increased from 0 to 2.

The second observation indicates that with as little topology knowledge as the 2-hop neighborhood in a graph with diameter 8 hops, we can achieve latency results almost as low as what store-and-forward routing on a shortest path would yield.

Finally we study how the mean maximum latency varies in conjunction with topology dissemination overhead in such random networks as a function of scope k. We focus on the p = 1.0 scenario since this is applies to general routing and not just duty cycling. We do not have an analytical mechanism for computing overhead, hence it is computed as follows:

1) Given graph G = (V, E), for each node u, compute the subgraph G v (k) induced by the vertices in the k hop neighborhood of u. The number of edges in

G v (k) is E v (k).
2) The normalized mean overhead per node is given by

Ohd(G, k) = v∈V E v (k)/(|V ||E|).
We plot both metrics computed (and averaged) over 10 random instances of RGGs with n = 100 and r = cr(100) in Figure 8 side-by-side. It can be observed that as the dissemination scope k goes up from 0 (pure random walk) to 8 (pure shortest path), the mean latency between the farthest pair of nodes drops significantly and Ohd(k) increases with k.

A key observation from Figure 8 is that both the latency and overhead curves have an inflection point at k = 2, i.e., the latency drops gradually after k = 2 and the overhead increases n and the analytical dependence of end-to-end latency between the farthest source-destination pair when using the hybrid random-walk/link state protocol as a function of duty-cycling probability p and dissemination scope k. more sharply. This indicates that k = 2 is a good value to operate the protocol at.

V. RELATED WORK

Lu et al. have studied the problem of finding minimum endto-end delay paths through duty cycling networks [START_REF] Lu | Delay Efficient Sleep Scheduling in Wireless Sensor Networks[END_REF]. They do not attempt to give expressions for latency, nor do they study how limited topology knowledge would affect performance.

Our prior work was focused on deriving exact expressions for latency of random walks between any source-destination pair in a finite graph. We studied the duty cycling case in particular [START_REF] Basu | Opportunistic Forwarding in Wireless Networks with Duty Cycling[END_REF] and then generalized it to general weighted graphs with node-specific sojourn times [START_REF] Chau | Exact Analysis of Latency of Stateless Opportunistic Forwarding[END_REF]. However we only studied purely stateless forwarding in the aforementioned papers and did not consider the effect of topology knowledge.

The Hazy-Sighted Link State routing (HSLS) protocol which belongs to a family of "fuzzy-sighted" approaches [START_REF] Santivanez | Making link-state routing scale for ad hoc networks[END_REF] adapts the scope of link-state broadcasts over space and time to significantly reduce the overhead of flat link-state routing. They give scaling laws for overhead in terms of network size but do not perform exact analysis of routing on any given topologies (which is the focus of our paper).

Weak State Routing (WSR) is a recently proposed routing mechanism for large-scale highly dynamic networks [START_REF] Acer | Weak state routing for large scale dynamic networks[END_REF]. WSR uses random directional walks biased occasionally by weak indirection state information (which is interpreted not as absolute truth, but as probabilistic hints) in intermediate VI. CONCLUSION AND FUTURE WORK We studied the effect of limited topology knowledge on the latency performance of random walk under light traffic loads. We first derived expressions for end-to-end latency in a Manhattan routing scenario. We then proposed RANDWLS, a hybrid routing protocol that performs limited-scope dissemination of link-state updates and random walks a packet until it hits any node with shortest path routing information about the destination. We gave an exact analysis for the mean latency performance of this protocol and observed that for random geometric graphs at the critical connectivity radius, the latency drops sharply as the dissemination scope is increased. At the same time the overhead due to topology dissemination starts increasing sharply beyond a certain initial scope (it flattens out at the end due to boundary effects). Such analysis gives us a valuable tool to make these predictions systematically without performing time-consuming simulations. In this paper we only studied the scenario where nodes only know their neighbor's schedules. Presumably if nodes know more information (e.g., schedules of k-hop neighbors), then the latency could be further reduced. The principal sources of latency here are waiting time for node wake up and the routing latency. Latency due to network congestion is an interesting topic for future research.

A -1 =               n -1 2(n -2) 2(n -
In this paper, the value of k was kept constant throughout the network. In general, it may be more suitable to vary k depending on where a particular node is located in the network topology. This can yield another degree of freedom in controlling the latency and overhead metrics. A detailed analysis of the aforementioned subject is a topic of future research.

We also assumed in this paper that topology information within k hops of a destination node is fresh and that shortest path routing will work accurately once a packet hits the khop boundary of a destination. In dynamic networks, this is not always the case, and the reliability of shortest path routing may drop significantly with increase in k. This tradeoff needs to be carefully analyzed to choose an appropriate value of k.

Finally, shortest path routing in a k-hop neighborhood may not yield the optimal latency, especially in low duty cycle regimes (i.e. low values of p), where longer paths can yield lower latency. To facilitate optimal latency routing, nodes need to disseminate their wake-up schedule information within their k-hop neighborhood. Analysis of the effect of k and p on the choice of optimal latency routes is a topic of future research.

in the following matrix form,

A      H 1,n H 2,n
. . .

H n-1,n      =      1/p 1/(1 -(1 -p) 2 )
. . .

1/(1 -(1 -p) 2 )      , ( 15
)
where A is the n -1 × n -1 invertible tridiagonal matrix:

A =          1 -1 0 . . . 0 0 -1/2 1 -
H n-1,n      = A -1      1/p 1/(1 -(1 -p) 2 )
. . .

1/(1 -(1 -p) 2 )      , ( 17
)
where the matrix inverse A -1 is a n -1 × n -1 matrix that can be obtained in an explicit form as shown in Figure 9. Thus, we read off the solution for H m,n as,

H m,n = n -m p + n-m j=1 2j + (m -2)(2(n -m)) 1 -(1 -p) 2 = n -m p + (n -m)(n -m + 1) + (m -2)(2(n -m)) 1 -(1 -p) 2 = (n -m) 1 p + m + n -3 1 -(1 -p) 2 , ( 18
)
which concludes the proof.

Fig. 1 .

 1 Fig. 1. Latency in a two-dimensional lattice with Manhattan routing

Fig. 2 .

 2 Fig. 2. Latency in a two-dimensional lattice (n is half of the Manhattan distance between source and destination nodes)

Fig. 4 .

 4 Fig. 4. A line lattice with N nodes. The source and destination nodes are numbered m and n respectively, with m < n. The k-hop neighborhood is shown using the shaded area, which contains nodes in [nk, n + k]. Under the k-hop topology-knowledge model, as soon as the packet hits the k-hop boundary of the destination node n (in this case node nk), the packet knows the exact location of n, and travels to n hop by hop, taking on an average k/p time slots where p is the pseudo-random duty-cycling rate.

Fig. 3 .

 3 Fig. 3. (a) Random walk issued from node 40 destined for node 14 before it hits the k-hop (k = 2) neighborhood of node 14. The blue edges indicate the path taken by the random walk until it hits node 5 which is exactly k hops away from node 14. The red edges indicate the shortest path to the destination from that point onward; (b) k-hop neighborhood replaced by a single node.

Fig. 5 .

 5 Fig. 5. (a) Mean hitting time Hm,n on 1-D network containing N = 20 nodes, for k-hop topology knowledge with RANDWLS scheme. The floor of the 3D plot corresponds to full topology knowledge (k = 20). The two other contours correspond to k = 10, and k = 0 (no topology knowledge); (b) Average hitting time Hm,n as a function of k when averaged over a uniformly random choice of m and n.

Fig. 6 .

 6 Fig. 6. Comparison between analytical and simulation results for a 20 node random geometric graph at the critical connectivity radius. The blue points indicate simulation results averaged over the specified number of runs whereas the red dots indicate the analytical results as predicted by Equation 14.

Fig. 7 .

 7 Fig. 7. A 100 node random geometric graph at the critical connectivity radius, cr(n) ≈

Fig. 8 .

 8 Fig. 8. Latency vs overhead analysis for random geometric graph G(100,cr(100) as a function of topology dissemination scope k for p = 1.0: (a) Mean latency as computed from Equation 14; (b) Mean normalized overhead computed per node. The results are averaged over 10 instances of RGGs with the same parameters.

  Replace nodes in Γ k v with a terminal node t and edges e k ∈ E k with set E k = {e = (u, t)|u ∈ ∆ k+1

	d 5) Assign weights to edges in E k as follows. For node }. u ∈ ∆ k+1 d